#include <bits/stdc++.h>
const int N = 1e6 + 5;
using namespace std;
int n, m, nxt[N], sum;
string a, b;
void build_nxt()
{
n = a.size() - 1;
nxt[1] = 0;
for (int i = 2, j = 0; i <= n; i++)
{
while (j > 0 && a[i] != a[j + 1])
{
j = nxt[j];
}
if (a[i] == a[j + 1])
{
j++;
}
nxt[i] = j;
}
}
void kmp()
{
m = b.size() - 1;
for (int i = 1, j = 0; i <= m; i++)
{
while (j && b[i] != a[j + 1])
{
j = nxt[j];
}
if (b[i] == a[j + 1])
{
j++;
}
if (j == m)
{
sum++;
}
}
}
int main()
{
cin >> n >> m >> a >> b;
build_nxt();
kmp();
cout << sum << endl;
return 0;
}
WA0
数据:
10 3
abababaaba
aba
输出 1
