Pagini recente » Cod sursa (job #1937783) | Cod sursa (job #119731) | Cod sursa (job #346722) | Cod sursa (job #1490753) | Cod sursa (job #919239)
Cod sursa(job #919239)
#include<stdio.h>
#include<string.h>
#define max 2000005
char pat[max],txt[max];
int pos[1069],pi[max],n,m;
void ComputePref()
{
pi[1]=0;
int i,q=0;
for(i=2;i<=m;++i)
{
while( q && pat[q+1] != pat[i] )
q=pi[q];
if(pat[q+1] == pat[i])
++q;
pi[i]=q;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(pat,sizeof(pat),stdin);
fgets(txt,sizeof(txt),stdin);
m=strlen(pat)-1;
n=strlen(txt)-1;
for(int i=m;i>=1;i--) pat[i]=pat[i-1]; pat[0]=' ';
for(int i=n;i>=1;i--) txt[i]=txt[i-1]; txt[0]=' ';
ComputePref();
int q=0,z=0;
for(int i=1;i<=n;++i)
{
while( q && pat[q+1] != txt[i])
q=pi[q];
if(pat[q+1]==txt[i])
q++;
if(q==m)
{
q=pi[m];
z++;
if(z<=1000)
pos[z]=i-m;
}
}
printf("%d\n",z);
for(int i=1;i<= ( z<=1000 ? z : 1000 ); ++i)
printf("%d ",pos[i]);
printf("\n");
return 0;
}