AcWing 831. KMP字符串
原题链接
简单
作者:
大蒟蒻er
,
2024-01-28 15:39:42
,
所有人可见
,
阅读 46
C++ 代码
#include <iostream>
using namespace std;
const int N = 1e5+10, M = 1e6+10;
int m, n , ne[N];
char s[M], p[N];
int main()
{
//从下标为1开始读入串
cin >> n >> p + 1 >> m >> s + 1;
//如果第一个字符就匹配失败只能重新匹配,所以ne[1] 固定 = 0, i 从2开始遍历_
//遍历模式串求ne[]数组
for (int i = 2,j = 0; p[i]; ++ i)
{
while (j && p[i] != p[j+1]) j = ne[j];
if (p[i] == p[j+1]) ++ j;
ne[i] = j;
}
// 上下两个j都表示已经匹配的字符个数
// 如果模式串长度比原串还要大可以直接判定失败
if (m >= n)
{
// 遍历原串求解
for (int i = 1, j = 0; s[i]; ++ 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];
}
}
}
}