KMP

To mathc string in linear time.

Algorithm

The main idea is to utilize the previous successful matching information to skip the impossible string comparison and construct the next array.

Definition[array next of pattern string P]
next[i] means that in substring P[0:i], the largest k such that the first k characters equal to the last k characters, and k can not take i + 1.

Caculate array next

If next[0], next[1], …, next[x - 1] are known, how to calculate next[x] efficiently?
Let next[x - ] = now,

• If P[x] = P[now], then next[x] = now + 1;
  
• If P[x] != P[now], then set now as the largest k such that k-prefix of A which equals to the k-suffix of B, where k can not take now;
  

int KMP(string s, string p) {
    int* next = new int[p.length()];
    next[0] = 0;
    int i = 1, now = 0;
    while (i < p.length()) {
        if (p[now] == p[i]) next[i ++] = ++ now;
        else {
            if (now == 0) next[i ++] = 0;
            else now = next[now - 1];
        }
    }
    i = 0; int j = 0;
    while (i < s.length() && j < p.length()) {
        if (s[i] == p[j]) { ++ i; ++ j; }
        else { j = j == 0 ? 0 : next[j - 1]; }
    }
    delete[] next;
    if (j == p.length()) return i - j;
    return -1;
}