KMP

Summary

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

OJ

 TrickDifficulty
LC 1392Naive Pi5-6 points
LC 796Pi on B + "#" + A3-4 points
LC 214Pi on A + "#" + A[::-1]5-6 points
LC 28Pi on B + "#" + A3-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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *