KMP字符串匹配
Skyzhou666 · · 算法·理论
KMP
哎呀好麻烦，嗯背得了（
#include <iostream>
#define MAXN 1000001
using namespace std;
int kmp[MAXN];
int main()
{
string a, b;
cin >> a >> b;
a = ' '+a; b = ' '+b;
int la = a.length(), lb = b.length();
for(int x = 2, y = 0; x <= lb; x++)
{
while(y && b[x] != b[y+1]) y = kmp[y];
if(b[y+1] == b[x]) y++;
kmp[x] = y;
}
for(int x = 1, y = 0; x <= la; x++)
{
while(y && b[y+1] != a[x]) y = kmp[y];
if(b[y+1] == a[x]) y++;
if(y == lb-1)
{
cout << x - lb + 2 << endl;
y = kmp[y];
}
}
for(int x = 1; x < lb; x++) cout << kmp[x] << " ";
cout << endl;
return 0;
}