Pagini recente » Cod sursa (job #254542) | Cod sursa (job #2420513) | Cod sursa (job #1046760) | Cod sursa (job #1977393) | Cod sursa (job #629501)
Cod sursa(job #629501)
#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 A1[2000005],B1[2000005];
int v1[2000005];
int hasha,hashb;
int Compara(int a, int b)
{
for(int j=a;j<=a+b-1;j++)
if(A1[j-a]!=B1[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++)
{
A1[i]=(int)A[i];
hasha=(hasha*P+A1[i])%M;
if(i>0)
{
k*=P;
k%=M;
}
}
for(i=0;i<NB;i++)
B1[i]=(int)B[i];
for(i=0;i<NA;i++)
hashb=(hashb*P+B1[i])%M;
if(hasha==hashb && Compara(0,NA)==1)
v1[++v1[0]]=0;
for(i=1;i<=NB-NA;i++)
{
hashb = (hashb - (B1[i-1]*k) % M);
if (hashb < 0) {
hashb += M;
}
hashb*=P;
hashb+=B1[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++)
fprintf(s,"%d ",v1[i]);
fclose (s);
return 0;
}