Pagini recente » Cod sursa (job #2494051) | Cod sursa (job #2310090) | Cod sursa (job #1320633) | Cod sursa (job #2227591) | Cod sursa (job #191277)
Cod sursa(job #191277)
#include <string.h>
#include <stdio.h>
#define N 2000010 //lungimea sirului
#define M 2000010 //lungimea subsirului
char sir[N],subsir[M];
long pi[M];
long stiva[1010],vf=0;
void adauga(long p)
{stiva[vf++]=p;}
void prefix()
{long i,k;
pi[1]=0;
for (i=2;i<strlen(subsir);i++)
{for(k=i-1;k>0&&subsir[i]!=subsir[pi[k]+1];k=pi[k])
{}
if(k>0)
{pi[i]=pi[k]+1;
}
else if(subsir[1]==subsir[i])
{pi[i]=1;
}
}
}
int main ()
{FILE *f,*fout;
f=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
long i,k,nr,n,m;
fgets(subsir,M,f);
fgets(sir,N,f);
for(i=strlen(subsir)+1;i>0;i--)
{subsir[i]=subsir[i-1];}
for(nr=0,i=strlen(sir)+1;i>0;i--)
{sir[i]=sir[i-1];}
subsir[0]=' ';sir[0]=' ';
subsir[strlen(subsir)-1]=subsir[strlen(subsir)];
prefix();
n=strlen(sir);
m=strlen(subsir);
for (i=1;i<=strlen(sir);)
{if(sir[i]==subsir[1])
{k=1;
while(k<=m&&k+i<=n&&sir[i+k]==subsir[k+1])
k++;
if(k==m-1)
{if(nr<1000)adauga(i);
nr++;
}
if(pi[k]>0)
{i+=k-pi[k];
}
else
{i++;}
}
else i++;
}
fprintf(fout,"%ld\n",nr);
for (i=0;i<vf;i++)
{fprintf(fout,"%ld ",stiva[i]-1);
}
fclose(fout);
return 0;
}