Pagini recente » Cod sursa (job #1238346) | Cod sursa (job #1264275) | Cod sursa (job #2129945) | Cod sursa (job #641181) | Cod sursa (job #354421)
Cod sursa(job #354421)
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
int phi[2000001];
char a[2000010], b[2000010];
char output[10000], nr[10];
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
int i, j, k, lena, lenb, cnt;
fgets(a, 2000010, stdin);
lena = strlen(a);
fgets(b, 2000001, stdin);
lenb = strlen(b);
k = -1;
phi[0] = -1;
for(i = 1; i < lena - 1; ++i)
{
while(k != -1 && a[k + 1] != a[i])
{
k = phi[k];
}
if(a[k + 1] == a[i])
{
++k;
}
phi[i] = k;
}
k = -1;
cnt = 0;
for(i = 0; i < lenb - 1; ++i)
{
while(k != -1 && a[k + 1] != b[i])
{
k = phi[k];
}
if(a[k + 1] == b[i])
{
++k;
}
if(k == lena - 2 && cnt < 1000)
{
++cnt;
sprintf(nr, "%d ", i - lena + 2);
strcat(output, nr);
k = phi[k];
}
}
printf("%d\n", cnt);
fputs(output, stdout);
return 0;
}