Cod sursa(job #1735816)

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