Pagini recente » Cod sursa (job #1799272) | Cod sursa (job #2075158) | Cod sursa (job #2357677) | Cod sursa (job #1801155) | Cod sursa (job #1277416)
#include <stdio.h>
#include <string.h>
#define N 2000000
#define P 73
#define MOD1 100007
char A[N+1], B[N+1],match[N];
int main()
{
FILE *fin,*fout;
fin=fopen("strmatch.in","r");
fout=fopen("strmatch.out","w");
int n=0,m=0;
A[0]=fgetc(fin);
while(A[n]!='\n')
A[++n]=fgetc(fin);
B[0]=fgetc(fin);
while(B[m]!='\n'&&B[m]!=EOF)
B[++m]=fgetc(fin);
int P1=1,P2=1,hashA1=0,hashA2=0;
int i,hash1=0;
for(i=0;i<n;i++){
hashA1=(hashA1*P+A[i])%MOD1;
hash1=(hash1*P+B[i])%MOD1;
if(i!=0)
P1=(P1*P)%MOD1;
}
int nr=0;
if(hash1==hashA1){
match[0]=1;
nr=1;
}
for(i=n;i<m;i++){
hash1=((hash1-(B[i-n]*P1)%MOD1+MOD1)*P+B[i])%MOD1;
if(hash1==hashA1){
int pp=0,j=0;
while(j<n&&pp==0){
if(A[j]!=B[i-n+j+1])
pp=1;
j++;
}
if(pp==0){
match[i-n+1]=1;
nr++;
}
}
}
fprintf(fout,"%d\n",nr);
nr=0,i=0;
while(i<m&&nr<1000){
if(match[i]){
fprintf(fout,"%d ",i);
nr++;
}
i++;
}
return 0;
}