KMP is an algorithm that find the given pattern string in the pending string. Usually we would think of violent traversing the two strings using for loop. However the time complexity of this method is O(n)~O(mn). So the KMP can cut the times of loop.

Knuth-Morris-Pratt Algorithm

Here is the code of violent traversing.

vector<int> match(string a, string b, int n, int m) {
    vector<int> ans;
    for (i = 0; i < n - m + 1; i++) {
        for (j = 0; j < m; j ++) {
            if (a[i + j] != b[j]) break;
        }
        if (j == m) ans.push_back(i);
    }
    return ans;
}

The followings are the main ideas of KMP.

Given a string s which length is n, it’s longest common prefix-suffix function is fix[i]. That means from the first element to the ith element ( include i ), the length of the common prefix-suffix is fix[i].

Assume that we have looped to the ith element.

If the next point of both point is the same, then we found the answer.

If not, then we move the point fix[i] to fix[fix[i]] and do the step above until we find the answer.

Author: o_oyao

Link: http://dyingdown.github.io/2019/08/16/KMP/

License: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.