Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

dlda's blog

By dlda, 6 years ago, translation, In English,

I can not understand why this line j = i [j-1]; gives us the right position.

Explain why this working =)

vector<int> prefix_function (string s) {
	int n = (int) s.length();
	vector<int> pi (n);
	for (int i=1; i<n; ++i) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])  ++j;
		pi[i] = j;
	}
	return pi;
}
 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

too late but maybe this helps. https://www.youtube.com/watch?v=nJbNe0Yzjhw