Cod sursa(job #1735811)

Utilizator S7012MYPetru Trimbitas S7012MY Data 31 iulie 2016 05:29:56
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#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<<' ';
}