Pagini recente » Cod sursa (job #732328) | Cod sursa (job #3251644) | Cod sursa (job #3219366) | Cod sursa (job #301842) | Cod sursa (job #1097807)
#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=0;
for (i=1;i<m;++i)
{
while (q>0 && prim[q]!=prim[i])
q = urm[q-1];
if (prim[q] == prim[i])
++q;
urm[i] = q;
}
}
int main(void)
{
int i,q,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();
q=0;
for (i=0;i<n;++i)
{
while (q>0 && prim[q]!=secund[i])
q = urm[q-1];
if (prim[q]==secund[i])
++q;
if (q==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;
}