Pagini recente » Cod sursa (job #2906455) | Cod sursa (job #285054) | Cod sursa (job #2042611) | Cod sursa (job #3185765) | Cod sursa (job #629482)
Cod sursa(job #629482)
// hash2.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <fstream>
#include <string>
#define p 73
#define max_n 2000001
#define mod1 100021
#define mod2 100007
using namespace std;
ifstream f;
ofstream g;
string a,b;
int na,nb,match[max_n],i,hashA1,hashA2,hashB1,hashB2,p1,p2;
int sol[max_n],nr;
int main () {
f.open("strmatch.in");
g.open("strmatch.out");
f>>a;
f>>b;
na=a.length();
nb=b.length();
if (na>nb) {
g<<0;
return 0;
}
hashA1=hashA2=hashB1=hashB2=0;
p1=p2=1;
nr=0;
for (i=0; i<na; i++){
hashA1=(hashA1*p+a[i])%mod1;
hashA2=(hashA2*p+a[i])%mod2;
if (i) {
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
for (i=0; i<na; i++) {
hashB1=(hashB1*p+b[i])%mod1;
hashB2=(hashB2*p+b[i])%mod2;
}
if (hashA1==hashB1 && hashA2==hashB2) {
sol[0]=1;
nr++;
}
for (i=na; i<nb; i++) {
hashB1=((hashB1-(b[i-na]*p1)%mod1+mod1)*p+b[i])%mod1;
hashB2=((hashB2-(b[i-na]*p2)%mod2+mod2)*p+b[i])%mod2;
if (hashA1==hashB1 && hashA2==hashB2)
sol[i-na+1]=1;
}
nr=0;
for (i=0; i<nb; i++)
if (sol[i]==1) nr++;
g<<nr<<"\n";
if (nr>1000) nr=1000;
int x=0;
for (i=0; i<=nb && x<nr; i++)
if (sol[i]) {
g<<i<<" ";
x++;
}
f.close();
g.close();
return 0;
}