Pagini recente » Cod sursa (job #1867159) | Cod sursa (job #291726) | Cod sursa (job #1651252) | Cod sursa (job #1779898) | Cod sursa (job #2543589)
#include <iostream>
#include<fstream>
#include<cstring>
#define MOD1 100007
#define MOD2 100021
char a[2000001], b[2000001], ok[2000001];
int i, j, na, nb, ns1, ns2, nsa1, nsa2, p1, p2, nr;
using namespace std;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin.getline(a, 2000001);
fin.getline(b, 2000001);
na=strlen(a);
nb=strlen(b);
p1=p2=1;
nsa1=nsa2=0;
for(i=0;i<na;i++) {
nsa1=(nsa1*73+a[i])%MOD1;
nsa2=(nsa2*73+a[i])%MOD2;
if(i!=0) {
p1=(p1*73)%MOD1;
p2=(p2*73)%MOD2;
}
}
if(na>nb) {
fout<<"0";
}
else {
ns1=ns2=0;
for(i=0;i<na;i++) {
ns1=(ns1*73+b[i])%MOD1;
ns2=(ns2*73+b[i])%MOD2;
}
nr=0;
if(ns1==nsa1 && ns2==nsa2) {
ok[0]=1;
nr++;
}
for(i=na;i<nb;i++) {
ns1=((ns1-(b[i-na]*p1)%MOD1+MOD1)*73+b[i])%MOD1;
ns2=((ns2-(b[i-na]*p2)%MOD2+MOD2)*73+b[i])%MOD2;
if(ns1==nsa1 && ns2==nsa2) {
ok[i-na+1]=1;
nr++;
}
}
fout<<nr<<endl;
nr=0;
for(i=0;i<nb && nr<1000;i++) {
if(ok[i]) {
fout<<i<<" ";
nr++;
}
}
}
return 0;
}