Pagini recente » Cod sursa (job #653779) | Cod sursa (job #2927862) | Cod sursa (job #2760546) | Cod sursa (job #2230995) | Cod sursa (job #170061)
Cod sursa(job #170061)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2000010
char a[N],b[N];
int pi[N];
int sol[1001],count=0;
void citeste()
{
freopen("strmatch.in","r",stdin);
scanf("%s\n",a+1);
scanf("%s",b+1);
fclose(stdin);
}
void scrie()
{
freopen("strmatch.out","w",stdout);
printf("%d\n",count-1);
for(int i=1;i<count;i++) printf("%d ",sol[i]);
fclose(stdout);
}
void rezolva()
{ int i;
int n=strlen(a+1),m=strlen(b+1);
int k=0;
//pi=(int*)malloc((n+1)*sizeof(int));
pi[1]=0;
for(i=2;i<=n;i++)
{ while(k&&a[i]!=a[k+1]) k=pi[k];
if(a[k+1]==a[i]) k++;
pi[i]=k;
}
k=0;
for(i=1;i<=m;i++)
{ while(k&&b[i]!=a[k+1]) k=pi[k];
if(a[k+1]==b[i]) k++;
if(k==n)
{ count++;
if(count<=1000) sol[count]=i-n-1;
}
}
//free(pi);
}
int main()
{
citeste();
rezolva();
scrie();
return 0;
}