KMP算法学习笔记
AC_Lover
·
·
算法·理论
核心：next数组
代码：
```cpp
int j=0;
for (int i=2;i<=m;i++)
{
while (j && t[j+1]!=t[i]) j=ne[j];
if (t[j+1]==t[i]) j++;
ne[i]=j;
}
```
总代码：
```cpp
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int M=1000010;
int ne[M];
int main()
{
string s,t;
cin >> s >> t;
int n=s.length(),m=t.length();
s=" "+s,t=" "+t;
int j=0;
for (int i=2;i<=m;i++)
{
while (j && t[j+1]!=t[i]) j=ne[j];
if (t[j+1]==t[i]) j++;
ne[i]=j;
}
j=0;
for (int i=1;i<=n;i++)
{
while (j && t[j+1]!=s[i]) j=ne[j];
if (t[j+1]==s[i]) j++;
if (j==m)
{
int st=i-m+1;
cout << st << "\n";
j=ne[j];
}
}
for (int i=1;i<=m;i++) cout << ne[i] << " ";
cout << "\n";
return 0;
}
```