Pagini recente » Cod sursa (job #2851632) | Cod sursa (job #3260816) | Cod sursa (job #889535) | Cod sursa (job #1455195) | Cod sursa (job #156202)
Cod sursa(job #156202)
#include <stdio.h>
#include <string.h>
#define INF "strmatch.in"
#define OUF "strmatch.out"
const int NMAX=2000004;
const int LIM=1001;
char a[NMAX],b[NMAX];
int n,m,pi[NMAX];
void prefix()
{
int i,k;
k=0;pi[1]=0;
for(i=2;i<=n;++i)
{
while(k>0&&a[k+1]!=a[i]) k=pi[k];
if(a[k+1]==a[i]) ++k;
pi[i]=k;
}
}
int main()
{
FILE *in,*out;
in=fopen(INF,"r");
out=fopen(OUF,"w");
int i,k,nr=0,sol[LIM];
fscanf(in,"%s%s",a+1,b+1);
// fgets(a+1,NMAX,in);
// fgets(b+1,NMAX,in);
// printf("\n");
// printf("A: %d %s \nB:%d %s",n,a+1,m,b+1);
n=strlen(a+1);
m=strlen(b+1);
prefix();
k=0;
for(i=1;i<=m;++i)
{
while(k>0&&a[k+1]!=b[i]) k=pi[k];
if(a[k+1]==b[i]) ++k;
if(k==n)
{
++nr;
if(nr<LIM) sol[nr]=i-n;
}
}
fprintf(out,"%d\n",nr);
for(i=1;i<=nr&&i<LIM;++i) fprintf(out,"%d ",sol[i]);
fclose(in);fclose(out);
return 0;
}