KMP
分析
只是kmp的话不算难 但它难在好多变形 要非常深入理解很多细节……
从1开始：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
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 <= m; i ++ )
{
while (j && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j ++ ;
if (j == n)
{
//匹配成功的操作
//printf("%d ", i - n);
//……
j = ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
}
}
return 0;
}
从0开始
#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n, m;
char s[N], p[N];
int ne[N];
int main()
{
cin >> m >> p >> n >> s;
ne[0] = -1;
for (int i = 1, j = -1; i < m; i ++ )
{
while (j >= 0 && p[j + 1] != p[i])
j = ne[j];
if (p[j + 1] == p[i])
j ++ ;
ne[i] = j;
}
for (int i = 0, j = -1; i < n; i ++ )
{
while (j != -1 && s[i] != p[j + 1])
j = ne[j];
if (s[i] == p[j + 1])
j ++ ;
if (j == m - 1)
{
//匹配成功的操作
//printf("%d ", i - n);
//……
j = ne[j];//还原现场 因情况而定 可以省略 也可能是从头开始 j=0;
}
}
return 0;
}
题目：
之前都是把找的题都刷完才结束一块的……第一次写到心态爆炸 以后有缘再见……kmp
💬 评论