作者:
NCpaste
,
2023-05-26 14:17:28
,
所有人可见
,
阅读 4
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
char p[N];
char s[M];
int nxt[N];
void kmp(int n, int m)
{
nxt[1] = 0;
int i, k, j;
i = 1;
k = 0;
while (i <= n)
{
if (!k || p[i] == p[k]) nxt[++i] = ++k;
else k = nxt[k];
}
i = j = 1;
while (i <= m)
{
while (j <= n && i <= m) {
if (!j || p[j] == s[i]) ++i, ++j;
else j = nxt[j];
}
if (j > n)
{
cout << i - j << " ";
j = nxt[j];
}
}
return ;
}
int main()
{
int n, m;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> p[i];
}
cin >> m;
for (int i = 1; i <= m; i++)
{
cin >> s[i];
}
kmp(n, m);
}
/*
100
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7x
500
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNA6fQNNluS6Uo12Lhd2UMUVm8bd6xNhNNyg1SNvvKvavJGn77RNjqBNNNg2UUUfkLLLs8Q47B85u8jrNeNNqWxAzvB9Sgv9vBfxnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNVF3NVsgUOUUxjULxAU44PU788P8se0LNpSfffvvkvvvnKyosnNEN2KNNgU3OUxkLuLLx44vixt08OsNNNN5ZtAfvOvsvivpv72
0 100 300
*/
/*
10
jNNNNjNNNN
30
jNNPw9NNNNnNMANTNHGNjNNNNjNNNN
20
*/