kmp

算法

求解给定一个模式串和一个主串，求模式串在主串中出现的位置(字符串的下标均从1开始)

算法思路

1. 取最长的相等前后缀，可以保证不漏解
2. 通过模式串前后缀的自我匹配的长度，计算函数，给指针打一张表，失配时就跳到的位置继续匹配

函数：表示模式串中相等前后缀的最长长度

如何计算函数

双指针：扫描模式串，扫描前缀

初始化：

1. 若，让回跳能匹配的位置，如果找不到能匹配的位置，回跳到
2. 若，让,指向匹配前缀的末尾
3. 等于的值

计算函数模板

ne[1]=0;
for(int i=2,j=0;i<=n;i++){
    while(j&&p[i]!=p[j+1]) j=ne[j];
    if(p[i]==p[j+1]) j++;
    ne[i]=j;
}

时间复杂度分析

指针所走的总步数就决定了总的执行次数

每轮循环，至多，那么一共向右至多走步，往左跳的步数加起来不会超过步，否则变为负数

故的总步数不会超过，所以时间复杂度为

模式串与主串匹配算法模板

for(int i=1,j=0;i<=n;i++){
    while(j&&s[i]!=p[j+1]) j=ne[j];
    if(s[i]==p[j+1]) j++;
    if(j==n) printf("%d\n",i-n+1);
}