Pagini recente » Cod sursa (job #899516) | Cod sursa (job #1417636) | Cod sursa (job #2430369) | Cod sursa (job #643098) | Cod sursa (job #613352)
Cod sursa(job #613352)
#include <fstream>
#include <cstring>
#define max_n 2000001
#define P 73
#define mod1 100007
#define mod2 100021
using namespace std;
char a[max_n],b[max_n];
int na,nb,i,cod1,cod2,h1,h2,x,nr,p1,p2;
int v[max_n];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main () {
in.getline(a,max_n);
in.getline(b,max_n);
na=strlen(a);
nb=strlen(b);
p1=p2=1;
if (na>nb) {
out << '0' << '\n';
return 0;
}
cod1=cod2=0;
for (i=0; i<na; i++) { //hash pt model
cod1=(cod1*P+a[i])%mod1;
cod2=(cod2*P+a[i])%mod2;
if (i) {
p1=(p1*P)%mod1;
p2=(p2*P)%mod2;
}
}
h1=h2=0;
for (i=0; i<na; i++) { //hash pentru prima bucata din string
h1=(h1*P+b[i])%mod1;
h2=(h2*P+b[i])%mod2;
}
nr=0;
if (cod1==h1 && cod2==h2) {
v[0]=1;
nr++;
}
for (i=na; i<nb; i++) {
h1=((h1-(b[i-na]*p1)%mod1+mod1)*P+b[i])%mod1;
h2=((h2-(b[i-na]*p2)%mod2+mod2)*P+b[i])%mod2;
if (h1==cod1 && h2==cod2) {
v[i-na+1]=1;
nr++;
}
}
out << nr << '\n';
x=0;
for (i=0; i<nb && x<1000; i++) {
if (v[i]) {
out << i << ' ';
x++;
}
}
return 0;
}