Pagini recente » Cod sursa (job #1525356) | Cod sursa (job #2559841) | Cod sursa (job #640112) | Cod sursa (job #2970416) | Cod sursa (job #2283011)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int n , m, phiA[NMAX], v[1005];
char a[NMAX], b[NMAX];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(a + 1);
gets(b + 1);
int n = (int)strlen(a + 1), m = (int)strlen(b + 1);
//construct phiA
int k = 0;
phiA[1] = 0;
for (int i = 2; i<=n; ++i)
{
while (k > 0 && a[i] != a[k + 1])
k = phiA[k];
if (a[i] == a[k + 1])
++k;
phiA[i] = k;
}
//construct phiB
k = 0;
int cnt = 0;
for (int i = 1; i<=m; ++i)
{
while (k > 0 && a[k + 1] != b[i])
k = phiA[k];
if (a[k + 1] == b[i])
++k;
if (k == n){
if (cnt < 1000)v[++cnt] = i;
else cnt++;}
}
printf("%d\n", cnt);
for (int i = 1; i<=min(cnt , 1000); ++i)
printf("%d ", v[i] - n);
printf("\n");
return 0;
}