kmp

模板题：洛谷P3375

code：

前缀函数解法

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
string s,t;
int n,m;
int pi[N];
int main(){cin>>s>>t;n=s.size();m=t.size();s=' '+t+'#'+s;for(int i=2;i<=n+m+1;i++){int j=pi[i-1];while(j&&s[i]!=s[j+1])j=pi[j];if(s[i]==s[j+1])j++;pi[i]=j;if(j==m){cout<<i-2*m<<endl;}}for(int i=1;i<=m;i++)cout<<pi[i]<<' ';cout<<endl;return 0;
}

next数组解法

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
string s,t;
int n,m;
int ne[N];
void kmp(){n=s.size();m=t.size();s=' '+s;t=' '+t;//预处理模式串的next数组for(int i=2,j=0;i<=m;i++){while(j&&t[i]!=t[j+1])j=ne[j];if(t[i]==t[j+1])j++;ne[i]=j;}//利用next数组匹配for(int i=1,j=0;i<=n;i++){while(j&&s[i]!=t[j+1])j=ne[j];if(s[i]==t[j+1])j++;if(j==m){cout<<i-m+1<<endl;}}
}
int main(){cin>>s>>t;kmp();for(int i=1;i<t.size();i++){cout<<ne[i]<<' ';}cout<<endl;return 0;
}