amankbps's blog

By amankbps, history, 2 years ago, In English

I want to solve this problem https://mirror.codeforces.com/contest/1029/problem/A but unable to implement that finding the period of substring in string if someone share approach it will great help

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use longest_prefix_suffix

void solve(int* lps, string pattern, int m)
{
	lps[0] = 0;
	int i = 1;
	int j = 0;
	while (i < m)
	{
		if (pattern[i] == pattern[j])
		{
			lps[i] = j + 1;
			j++;
			i++;
		}
		else
		{
			if (j != 0)
				j = lps[j - 1];
			else
			{
				lps[i] = 0;
				i++;
			}
		}
	}
	return;
}
int main()
{
	int n, k;
	cin >> n >> k;
	string s;
	cin >> s;
	int *lps = new int[n]();
	solve(lps, s, n);
	int counter = lps[n - 1];
	cout << s;
	for (int i = 1; i < k; i++)
		cout << s.substr(counter, n - counter);
	cout << endl;
	return 0;
}
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

just put a blog on codeforces and wait for responses:)

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

ummm for that problem since $$$n,k \leq 50$$$ you can literally brute force it (create a separate string and keep adding occurrences of a prefix of $$$t$$$ and see if $$$t$$$ eventually becomes a prefix of that string). This runs in $$$n^2$$$ which is more than enough lol

But if you're a gigachad and want to solve a harder version of this problem on CSES you can try using string hashing (my editorial, definitely not a shameless plug) or use the kmp thing in the editorial (why is that even there in the editorial for a div 3 A)