Pagini recente » Cod sursa (job #1786310) | Cod sursa (job #1354006) | Cod sursa (job #1269527) | Cod sursa (job #2820798) | Cod sursa (job #2283022)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 2000005;
int n = 0, m = 0, phiA[NMAX], v[1005];
char a[NMAX], b[NMAX];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
char c;
scanf("%c", &c);
while (c != '\n')
{
a[++n] = c;
scanf("%c", &c);
}
scanf("%c", &c);
while (c != '\n')
{
b[++m] = c;
scanf("%c", &c);
}
a[n + 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;
}