Pagini recente » Cod sursa (job #2689333) | Cod sursa (job #5644) | Cod sursa (job #2641028) | Cod sursa (job #1529781) | Cod sursa (job #327252)
Cod sursa(job #327252)
#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,20000000);
fin.getline(b,20000000);
n=strlen(a);
m=strlen(b);
P1=P2=1;
for(i=0;i<n;i++){
hash1A=(hash1A*73+a[i])%PR1;
hash2A=(hash2A*73+a[i])%PR2;
if(i>0){
P1=(P1*73)%PR1;
P2=(P2*73)%PR2;
}
}
for(i=0;i<n;i++){
hash1=(hash1*73+b[i])%PR1;
hash2=(hash2*73+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)*73+b[i])%PR1;
hash2=(((hash2-b[i-n]*P2)%PR2+PR2)*73+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';
fin.close();
fout.close();
return 0;
}