Pagini recente » Cod sursa (job #2970417) | Cod sursa (job #2098711)
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
FILE *f,*g;
char x[2000004],y[2000004];
int pi[2000004],d[2000004],v[2000004];
int main()
{
int i,k,m,n,nr=0;
f=fopen("strmatch.in","r");
g=fopen("strmatch.out","w");
fgets(x+1,2000002,f);
fgets(y+1,2000002,f);
m=strlen(x+1)-1;
n=strlen(y+1)-1;
k=0;
pi[1]=0;
for(i=2;i<=m;i++)
{
while(k>0 && x[i]!=x[k+1])
k=pi[k];
if(x[k+1]==x[i])
k++;
pi[i]=k;
}
k=0;
for(i=1;i<=n;i++)
{
while(k>0 && y[i]!=x[k+1])
k=pi[k];
if(y[i]==x[k+1])
k++;
d[i]=k;
}
for(i=1;i<=n;i++)
{
if(d[i]==m)
v[++nr]=i-m;
}
fprintf(g,"%d\n",nr);
for(i=1;i<=nr;i++)
fprintf(g,"%d ",v[i]);
fclose(f);
fclose(g);
return 0;
}