Pagini recente » Cod sursa (job #494538) | Cod sursa (job #2634282) | Cod sursa (job #1669353) | Cod sursa (job #1524524) | Cod sursa (job #657766)
Cod sursa(job #657766)
#include<iostream>
#include<fstream>
#include<string.h>
#include<vector>
#define N 2000010
#define M1 100007
#define M2 100021
#define P 73
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char a[N],b[N];
int la,lb,ha1,ha2,hb1,hb2,p1,p2;
vector<int> rez;
int main() {
int i;
in.getline(a,N);
in.getline(b,N);
la=strlen(a);
lb=strlen(b);
if(la>lb) {
out << "0\n";
return 0;
}
p1=p2=1;
for(i=0;i!=la;++i) {
ha1=(ha1*P + a[i])%M1;
ha2=(ha2*P + a[i])%M2;
hb1=(hb1*P + b[i])%M1;
hb2=(hb2*P + b[i])%M2;
if(i!=0) {
p1=(p1*P)%M1;
p2=(p2*P)%M2;
}
}
if(ha1==hb1 && ha2==hb2)
rez.push_back(1);
for(i=la;i!=lb;++i) {
hb1=((hb1 - (b[i - la] * p1) % M1 + M1) * P + b[i]) % M1;
hb2=((hb2 - (b[i - la] * p2) % M2 + M2) * P + b[i]) % M2;
if(ha1==hb1 && ha2==hb2)
rez.push_back(i-la+1);
}
out << rez.size() << "\n";
for(i=0;i!=rez.size() && i!=1001;++i)
out << rez[i] << " ";
return 0;
}