Pagini recente » Cod sursa (job #1048205) | Cod sursa (job #2476496) | Cod sursa (job #1371160) | Cod sursa (job #2901573) | Cod sursa (job #629534)
Cod sursa(job #629534)
#include <cstdio>
#include <string.h>
#define P 173
#define P1 191
#define M 666013
#define M1 193939
FILE *f,*s;
int NA,NB;
int i,j,k,k1,l,m,n;
char A[2000005],B[2000005];
int v1[2000005];
int hasha,hashb,hasha1,hashb1;
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;
k1=1;
for(i=0;i<NA;i++)
{
hasha=(hasha*P+(int)A[i])%M;
hasha1=(hasha1*P1+(int)A[i])%M1;
if(i>0)
{
k*=P;
k%=M;
k1*=P1;
k1%=M1;
}
}
for(i=0;i<NA;i++)
{
hashb=(hashb*P+(int)B[i])%M;
hashb1=(hashb1*P1+(int)B[i])%M1;
}
if(hasha==hashb && hasha1==hashb1/*Compara(0,NA)==*/)
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;
hashb1 = (hashb1 - ((int)B[i-1]*k1) % M1);
if (hashb1 < 0) {
hashb1 += M1;
}
hashb1*=P1;
hashb1+=(int)B[i+NA-1];
hashb1%=M1;
if(hasha==hashb && hasha1==hashb1/*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;
}