Pagini recente » Cod sursa (job #2615102) | Cod sursa (job #1325081) | Cod sursa (job #3254255) | Cod sursa (job #135125) | Cod sursa (job #629513)
Cod sursa(job #629513)
#include <cstdio>
#include <string.h>
#define P 173
#define M 666013
FILE *f,*s;
int NA,NB;
int i,j,k,l,m,n;
char A[2000005],B[2000005];
int v1[2000005];
int hasha,hashb;
int Compara(int a, int b)
{
for(int j=a;j<=a+b-1;j++)
if((int)A[j-a]!=(int)B[j]) return 0;
return 1;
}
int main()
{
f=fopen("strmatch.in","r");
s=fopen("strmatch.out","w");
fscanf(f,"%s\n%s",A,B);
NA=strlen(A);
NB=strlen(B);
if(NA>NB)
{
fprintf(s,"0");
return 0;
}
k=1;
for(i=0;i<NA;i++)
{
hasha=(hasha*P+(int)A[i])%M;
if(i>0)
{
k*=P;
k%=M;
}
}
for(i=0;i<NA;i++)
hashb=(hashb*P+(int)B[i])%M;
if(hasha==hashb && Compara(0,NA)==1)
v1[++v1[0]]=0;
for(i=1;i<=NB-NA;i++)
{
hashb = (hashb - ((int)B[i-1]*k) % M);
if (hashb < 0) {
hashb += M;
}
hashb*=P;
hashb+=(int)B[i+NA-1];
hashb%=M;
if(hasha==hashb && Compara(i,NA)==1)
v1[++v1[0]]=i;
}
fprintf(s,"%d\n",v1[0]);
for(i=1;i<=v1[0] &&i<=1000;i++)
fprintf(s,"%d ",v1[i]);
fclose (s);
return 0;
}