Блог пользователя amankbps

Автор amankbps, история, 2 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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)