Pagini recente » Cod sursa (job #1073848) | Cod sursa (job #1850040) | Cod sursa (job #2610252) | Cod sursa (job #382225) | Cod sursa (job #1097709)
#include <stdio.h>
#include <cstring>
using namespace std;
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
int m,n;
char prim[NMax], secund[NMax];
int urm[NMax], pos[1024];
void prefix(void)
{
int i,q=-1;
for (i=1;i<m;++i)
{
while (q>0 && prim[q+1]!=prim[i])
q = urm[q];
if (prim[q+1] == prim[i])
++q;
urm[i] = q;
}
}
int main(void)
{
int i,q=0,n=0,cont=0;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s",prim);
scanf("%s",secund);
m=strlen(prim);
n=strlen(secund);
prefix();
for (i=0;i<n;++i)
{
while (q>0 && prim[q+1]!=secund[i])
q = urm[q];
if (prim[q+1]==secund[i])
++q;
if (q==m-1)
{
q=urm[m];
++cont;
if (cont <= 1000)
pos[cont]=i-m+1;
}
}
printf("%d\n", cont);
for (i = 1; i <= minim(cont, 1000); ++i)
printf("%d ", pos[i]);
printf("\n");
return 0;
}