Pagini recente » Borderou de evaluare (job #1583670) | Cod sursa (job #1755810) | Cod sursa (job #1735816)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define B1 127
#define B2 131
#define M1 2000009
#define M2 2000011
using namespace std;
string p,s;
int hp1,hp2,pw1=1,pw2=1,hs1,hs2,nrs;
vector<int> r;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>p>>s;
if(p.size()>s.size()) {
g<<0;
return 0;
}
for(int i=0; i<p.size(); ++i) {
hp1=(hp1*B1+p[i])%M1;
hp2=(hp2*B2+p[i])%M2;
pw1=(pw1*B1)%M1; pw2=(pw2*B2)%M2;
hs1=(hs1*B1+s[i])%M1; hs2=(hs2*B2+s[i])%M2;
}
if(hs1==hp1 && hs2==hp2) {
r.push_back(0);
++nrs;
}
for(int i=p.size(); i<s.size(); ++i) {
hs1=(hs1*B1-pw1*s[i-p.size()]+s[i]+M1*256)%M1;
hs2=(hs2*B2-pw2*s[i-p.size()]+s[i]+M2*256)%M2;
if(hs1==hp1 && hs2==hp2) {
++nrs;
if(nrs<=1000) r.push_back(i-p.size()+1);
}
}
g<<nrs<<'\n';
for(auto i:r) g<<i<<' ';
}