Pagini recente » Cod sursa (job #1824308) | Cod sursa (job #1387062) | Cod sursa (job #2673233) | Cod sursa (job #282923) | Cod sursa (job #327246)
Cod sursa(job #327246)
#include<fstream.h>
long i,hash1,hash2,hash1A,hash2A,n,m,P1,P2,PR1=666013,PR2=999017,cate;
char a[2000001],b[2000001];
int sir[2000001];
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a,2000000000);
fin.getline(b,2000000000);
n=strlen(a);
m=strlen(b);
P1=P2=1;
for(i=0;i<n;i++){
hash1A=(hash1A*26+a[i])%PR1;
hash2A=(hash2A*26+a[i])%PR2;
if(i>0){
P1=(P1*26)%PR1;
P2=(P2*26)%PR2;
}
}
for(i=0;i<n;i++){
hash1=(hash1*26+b[i])%PR1;
hash2=(hash2*26+b[i])%PR2;
}
if(n>m){
fout<<"0"<<'\n';
return 0;
}
if(hash1==hash1A && hash2==hash2A){
sir[0]=1;
cate=1;
}
for(i=n;i<m;i++){
hash1=(((hash1-b[i-n]*P1)%PR1+PR1)*26+b[i])%PR1;
hash2=(((hash2-b[i-n]*P2)%PR2+PR2)*26+b[i])%PR2;
if(hash1==hash1A && hash2==hash2A){
sir[i-n+1]=1;
cate++;
}
}
fout<<cate<<'\n';
cate=0;
for(i=0;i<m && cate<1000;i++)
if(sir[i]==1){
fout<<i<<' ';
cate++;
}
fout<<'\n';
system("PAUSE");
return 0;
}