kmp算法模板

void kmp() {
    n = strlen(s + 1);   // s是目标串
    m = strlen(p + 1);  // p是模板串
    // nxt预处理开始
    int j = 0;
    nxt[1] = 0;
    for (int i = 2; i <= m; i++) {
        while (j > 0 && p[j + 1] != p[i]) /* 判断当前子串的前后缀相等的长度是否能增加或减少
        注意j>0不要漏，这就是为什么" "+字符串的原因*/
            j = nxt[j];
            if(p[j + 1] == p[i]) //同上 (增加)  
                j++;
            nxt[i] = j;
    }
        // 预处理结束
        // 匹配部分
    j = 0;
    for (int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))//j==m是已经到头了，也需要回退
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
        }
}
// 
//找有多少符合的串的数量
for (int i = 1; i <= n; i++) {
    if(f[i] == m) { //f[i]=模式串的长度时成立
        ans++;
    }
}
//算法复杂度为 n+m