KMP算法

思路：

首先计算出模板字符串每个位置的最长公共前后缀，通过最长公共前后缀可以在和原始字符串进行比较的时候只需要O(n)的时间比较完成。

而【计算模板字符串每个位置的最长公共前后缀】，【计算原始字符串和模板字符串的最长匹配公共前缀】是一样的做法。前者，模板字符串的前缀和当前后缀进行比较，记录每个位置匹配的最长前后缀，当前位置前缀串和后缀串相等的时候，其最长匹配前缀就是之前已经记录的最长匹配前缀加1，否则最长匹配长度缩小到前一个匹配的最长前缀，知道匹配的最长前缀为0。后者，不一样的是拿模板字符串作为前缀进行比较，其他和第一个问题一样。

具体可查看《算法导论》，b站的一些教学视频。

实现:

代码实现示例：

#include <iostream>
using namespace std;
int m, n;
char str[] = "@bacbababaabcbab";
char pattern[] = "@ababaca";
int pi[10];
int f[100000];
void compute_next(){
    int j = 0;
    pi[1] = 0;
    for(int i = 2; i <= m; i++){
        while(j > 0 && pattern[i] != pattern[j+1]) j = pi[j];
        if(pattern[i] == pattern[j+1])j++;
        pi[i] = j;
    }
}
void compute_f(){
    int j = 0; 
    for(int i = 1; i <= n; i++){
        while(j > 0 && str[i] != pattern[j + 1])j = pi[j];
        if(str[i] == pattern[j + 1])j++;
        f[i] = j;
    }
}
int main(){
    n = 15, m = 7;
    compute_next();
    compute_f();
    for(int i = 1; i <= n; i++){
        cout<<"i = "<<i<<", "<<f[i]<<endl;
    }
    return 0;
}

例题：