Pagini recente » Cod sursa (job #1121244) | Cod sursa (job #1764590) | Cod sursa (job #2355192) | Cod sursa (job #582569) | Cod sursa (job #208086)
Cod sursa(job #208086)
#include <cstring>
#include <cstdio>
#define N 2000003
char sir[N],sub[N];
long pi[N];
long poz[N],vf;
int main ()
{FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
fgets(sub,N,fin);
fgets(sir,N,fin);
long i,j,l1=strlen(sir),l2=strlen(sub);
l2--;
for (i=l1;i>=1;i--)
{sir[i]=sir[i-1];}
for (i=l2;i>=1;i--)
{sub[i]=sub[i-1];}
*sir=' ';
*sub=' ';
// for (i=1;i<=l1;i++) {pi[i]=1;}
for (j=0,i=2;i<=l2;i++)
{while(sub[j+1]!=sub[i]&&j>0)
{j=pi[j];
}
if(sub[j+1]==sub[i])
{j++;}
pi[i]=j;
}
for (vf=0,j=0,i=1;i<=l1;i++)
{while(sub[j+1]!=sir[i]&&j>0)
{j=pi[j];
}
if(sub[j+1]==sir[i])
{j++;
if(j==l2)
{poz[vf++]=i-l2;
j=pi[j];
}
}
}
fprintf(fout,"%ld\n",vf);
for (i=0;i<vf;i++)
{fprintf(fout,"%ld ",poz[i]);
}
fclose (fout);
return 0;
}