KMP模板

算法介绍

KMP是一种字符串匹配算法，可以求出一个字符串在另一个字符串中出现的次数。时间复杂度为O(N+M)

算法实现

算法分为预处理next数组和查询两步进行。

1.预处理

next数组表示从起始位置到当前位置最长的前缀和后缀的长度
那么，在处理时，我们就拿当前位置和原来匹配的最长前缀的后一位比较：

如果相同，那么长度+1,next[j−1]+1

如果不相同，那么根据此数组的性质，显而易见，你的相等的部分只能向前找也就是说，你的这个位置的next值会减小也就是去原来的最长相等前缀去找
所以，我们可以得到next数组的求解方法：每一次检查上一次最长前缀的后一个位置如果相等则next[j]=next[i]+1,否则令i=next[i−1]+1，继续循环匹配
其实这就是自己匹配自己的过程。这是最难理解的地方，多手算几遍就好了

2.查询

本算法难在于next预处理，如果你已经懂了，就很简单了
我们设定两个指针i，j，指向两个字符串。
如果i==j那么i++，j++如果失配，就令i=next[i−1]+1

模板代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

char str1[1000005],str2[1000005];
//str1是被匹配字符串，str2是匹配字符串
int Next[1000005];
vector <int> Ans;

inline void init(char *str){ //计算next数组
    int len,t;
    len = strlen(str);
    Next[0] = -1;
    for(int i = 1;i < len;i++){
        t = Next[i-1];
        while(str[t+1] != str[i] && t >= 0)
            t = Next[t];
        if(str[t+1] == str[i])
            Next[i] = t+1;
        else
            Next[i] = -1;
    }
}

void kmp(char *str1,char *str2){ //kmp查找
    init(str2);
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    int i = 0,j = 0;
    while(j < len1){
        if(str2[i] == str1[j]){  //相同
            i++;j++;
            if(i == len2){
                Ans.push_back(j-len2+1);
                i = Next[i-1]+1;
            }
        }
        else{  //失配，根据next数组寻找下一个位置
            if(i == 0)
                j++;
            else
                i = Next[i-1] + 1;
        }
    }
}

int main(){
    cin >> str1 >> str2;
    int l = strlen(str2);
    kmp(str1,str2);
    for(int i = 0;i < Ans.size();i++)
        printf("%d%c",Ans[i],'\n');
    for(int i = 0;i < l;i++){ //洛谷题目需要的输出next数组
        printf("%d ",Next[i] + 1);
    }
    return 0;
}

赏

谢谢你请我吃糖果