Pagini recente » Cod sursa (job #3224657) | Cod sursa (job #165855) | Cod sursa (job #2556568) | Cod sursa (job #1080671) | Cod sursa (job #288246)
Cod sursa(job #288246)
#include <stdio.h>
#include <string.h>
#define Nmax 2000000
#define Mmax 1001
int n,m,pi[Nmax],nr,vect[Mmax];
char a[Nmax],b[Nmax];
int minim(int a,int b)
{
if(a<b)
return a;
return b;
}
void generare()
{
int i,q=0;
pi[1]=0;
for(i=2;i<=n;++i)
{
while(q>0 && a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,q=0;
scanf("%s",a);
scanf("%s",b);
n=strlen(a);
m=strlen(b);
for(i=n;i;--i)
a[i]=a[i-1];
a[0]=' ';
for(i=m;i;--i)
b[i]=b[i-1];
b[0]=' ';
generare();
for(i=1;i<=m;++i)
{
while(q>0 && a[q+1]!=b[i])
q=pi[q];
if(a[q+1]==b[i])
++q;
if(q==n)
{
q=pi[n];
++nr;
if(nr<=1000)
vect[nr]=i-n;
}
}
printf("%d\n",nr);
q=minim(nr,1000);
for(i=1;i<=q;++i)
printf("%d ",vect[i]);
return 0;
}