Definition
Given a string of length , the prefix function at position is the length of the longest proper prefix of the substring
Given a string of length , the prefix function at position is the length of the longest proper prefix of the substring
Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:
that is also a suffix of this substring.
Here, a proper prefix means a prefix that is not equal to the entire string itself.
So we always have:
and for :
For example, for the string
the prefix function is
To compute the prefix function efficiently, we use several important observations.
For every , we have:
This means that the prefix value can increase by at most one when we move to the next position.
Suppose we already know .
Let
Then we try to extend the current match by comparing:
S[i]S[j]If they are equal, then we can increase the prefix length by one:
Otherwise, we cannot extend the current prefix, so we need to try a shorter one.
The next candidate is:
We repeat this process until:
If no match is found, then:
vector<int> prefix_function(string s) {
vector<int> p(s.size());
for (int i = 1; i < (int)s.size(); i++) {
int j = p[i - 1];
while (j > 0 && s[i] != s[j]) {
j = p[j - 1];
}
if (s[i] == s[j]) {
j += 1;
}
p[i] = j;
}
return p;
}