dlda's blog

By dlda, 9 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;
}

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it