Pagini recente » Cod sursa (job #451379) | Cod sursa (job #2481519) | Cod sursa (job #2972145) | Cod sursa (job #2751756) | Cod sursa (job #170216)
Cod sursa(job #170216)
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 2000010
char a[N],b[N];
int *pi;
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);
for(int i=1;i<=count&&i<=1000;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;
}
}
free(pi);
}
int main()
{
citeste();
rezolva();
scrie();
return 0;
}