Pagini recente » Cod sursa (job #57931) | Cod sursa (job #2563148) | Cod sursa (job #2136212) | Cod sursa (job #724558) | Cod sursa (job #662134)
Cod sursa(job #662134)
#include<fstream>
#include<cstring>
using namespace std;
int i,j,n,m,rez=0,urm[2000001],sol[1001];
char a[2000001],b[2000001];
void prefix()
{
int i,k=0;
for(i=2;i<=n;++i)
{
while(k&&a[k+1]!=a[i])
k=urm[k];
if(a[k+1]==a[i])
++k;
urm[i]=k;
}
}
void rezolva()
{
int i,k=0;
for(i=2;i<=m;++i)
{
while(k&&a[k+1]!=b[i])
k=urm[k];
if(a[k+1]==b[i])
++k;
if(k==n)
{
k=urm[n];
if(rez<=1000)
sol[++rez]=i-n;
}
}
}
int main()
{
FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
fscanf(f,"%s%s",a+1,b+1);
n=strlen(a+1);
m=strlen(b+1);
urm[1]=0;
prefix();
rezolva();
fprintf(g,"%d\n",rez);
for(i=1;i<=rez;++i)
fprintf(g,"%d ",sol[i]);
return 0;
}