KMP – FighterNan's Blog

Summary

In this post, I will introduce some problems related to KMP.

OJ

	Trick	Difficulty
LC 1392	Naive Pi	5-6 points
LC 796	Pi on B + "#" + A	3-4 points
LC 214	Pi on A + "#" + A[::-1]	5-6 points
LC 28	Pi on B + "#" + A	3-4 points

Details

Pi

$\pi[i] = \max_{k = 0 \dots i}{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]}$

$\pi[i]$ is the length of the longest prefix of substring $s[0\dots i]$ , such that this prefix is also the suffix of $s[0\dots i]$ . Note that this prefix excludes $s[0\dots i]$ itself. By the definition, we have $\pi[0] = 0$ . For example, we have,

$pi("abcabcd") = [0, 0, 0, 1, 2, 3, 0]$

$pi("aabaaab") = [0, 1, 0, 1, 2, 2, 3]$

Please refer to this wiki if you want to know how the following codes work.

vector<int> get_pi(string const&s) {
    int n = s.size();
    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];
        }
        pi[i] = j + (s[i] == s[j]);
    }
    return pi;
}

Summary

OJ

Details

Pi

Leave a Reply Cancel reply