Pagini recente » Diferente pentru utilizator/andrici_cezar intre reviziile 49 si 48 | Cod sursa (job #1735811)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define B1 57
#define B2 59
#define M1 1000007
#define M2 1000009
using namespace std;
string p,s;
int hp1,hp2,pw1=1,pw2=1,hs1,hs2,nrs;
vector<int> r;
int main() {
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
cin>>p>>s;
if(p.size()>s.size()) {
cout<<0;
return 0;
}
for(int i=0; i<p.size(); ++i) {
hp1=(hp1*B1+p[i]-'A')%M1;
hp2=(hp2*B2+p[i]-'A')%M2;
pw1=(pw1*B1)%M1; pw2=(pw2*B2)%M2;
s[i]-='A';
hs1=(hs1*B1+s[i])%M1; hs2=(hs2*B2+s[i])%M2;
}
//cout<<hp1<<' '<<hs1;
if(hs1==hp1 && hs2==hp2) {
r.push_back(0);
++nrs;
}
for(int i=p.size(); i<s.size(); ++i) {
s[i]-='A';
//cout<<hp1<<' '<<hs1<<' '<<hp2<<' '<<hs2<<'\n';
hs1=(hs1*B1-pw1*s[i-p.size()]+s[i]+M1)%M1;
hs2=(hs2*B2-pw2*s[i-p.size()]+s[i]+M2)%M2;
if(hs1==hp1 && hs2==hp2) {
++nrs;
if(nrs<=1000) r.push_back(i-p.size()+1);
}
}
cout<<nrs<<'\n';
for(auto i:r) cout<<i<<' ';
}