Pagini recente » Cod sursa (job #1057657) | Cod sursa (job #1956432) | Cod sursa (job #715202) | Cod sursa (job #1834978) | Cod sursa (job #662139)
Cod sursa(job #662139)
#include<fstream>
#include<cstring>
using namespace std;
int i,j,n,m,rez=0,urm[2000002],sol[1005];
char a[2000002],b[2000002];
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=1;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;
rez++;
}
}
}
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;
if(n>m)
fprintf(g,"0\n");
else
{
prefix();
rezolva();
fprintf(g,"%d\n",rez);
for(i=0;i<rez&&i<1000;++i)
fprintf(g,"%d ",sol[i]);
}
return 0;
}