字符串

定义

定义一个字符串 $s$ 的 border 为 $s$ 的一个非 $s$ 本身的子串 $t$ ，满足 $t$ 既是 $s$ 的前缀，又是 $s$ 的后缀。

KMP 详解

$kmp$ 预处理的本质是在处理以每个位置 $i$ 为结尾的字符串，求最大的 $border$ 。

$kmp$ 是一种优化的暴力的思想。

暴力是 $O(nm)$ ， $kmp$ 是 $O(n+m)$ 。

其关键在于优化字符串的匹配。

考虑每次匹配，若 $j+1$ 与 $i$ 可以匹配那么匹配，否则 $j$ 跳到上一个前后缀都是匹配的，后缀匹配是为了匹配文本串，前缀匹配时为了匹配自身，因此要这么做。

预处理模式串自身的 $ne$ ，首先对于第一个位置， $ne[1]=1$ ，剩下的同理维护一个双指针，因为前后缀长度 $+1$ 相当于时，前后缀的末尾同时匹配上一个新的，也就算是匹配了吧。

本质就是找到 $[1,j]$ 和 $[i-j+1,i]$ 的 $i$ 匹配的 $j$ 。

#include<iostream>
using namespace std;
int n,m;
const int N=1e6+8;
int ne[N];
void kmp(string s,int len){
    for(int i=2,j=0;i<=len;i++){
        while(j&&s[i]!=s[j+1]) j=ne[j];
        if(s[i]==s[j+1]) j++;
        ne[i]=j;
    }
}
int main(){
    string s,p;
	cin>>s>>p;
    n=s.length();
    m=p.length();
    s=" "+s;
    p=" "+p;
    kmp(p,m);
    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==m){
            printf("%d\n",i-m+1);
            j=ne[j];
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d ",ne[i]);
    }
    return 0;
}