Pagini recente » Cod sursa (job #1097802) | Cod sursa (job #599546) | Cod sursa (job #811841) | Cod sursa (job #1623982) | Cod sursa (job #166931)
Cod sursa(job #166931)
#include <stdio.h>
#include <string.h>
#define maxim 2000010
long n,m,i,k;
long p[maxim+3],sol[maxim+3];
char a[maxim+3],b[maxim+3];
void pi()
{
k=0;
for (i=2; i<=n; i++)
{
while (k && a[i]!=a[k+1])
k=p[k];
if (a[k+1]==a[i]) { k++; }
p[i]=k;
}
}
void kmp()
{
n=strlen(a+1)-1;
m=strlen(b+1)-1;
pi(); sol[0]=0; k=0; i=0;
for (i=1; i<=m; i++)
{
while (k && b[i]!=a[k+1])
k=p[k];
if (b[i]==a[k+1]) {k++;}
if (k==n) { sol[0]++; sol[sol[0]]=i-n; k=p[k]; }
}
}
int main(void)
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a+1, maxim, stdin);
fgets(b+1, maxim, stdin);
kmp();
printf("%ld\n",sol[0]);
if (sol[0]>1000) { sol[0]=1000; }
for (i=1; i<=sol[0] ;i++) { printf("%ld ", sol[i]); }
fclose(stdin); fclose(stdout);
return 0;
}