Cod sursa(job #1950546)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 3 aprilie 2017 09:43:21
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");

string P,S;
int np,ns;
int NM;
vector<int> M;

const int MOD1=10007;
const int MOD2=666013;
const int POW1=79;
const int POW2=73;
int HP1,HP2;
int HS1,HS2;
int POWMAX1,POWMAX2;

void read(){
    in>>P>>S;
    np=P.size();
    ns=S.size();
}
void hashes(){
    POWMAX1=1;
    POWMAX2=1;
    for(int i=0;i<np;i++){
        //pattern
        HP1=(1LL*HP1*POW1 + P[i])%MOD1;
        HP2=(1LL*HP2*POW2 + P[i])%MOD2;
        //
        if(i){
            POWMAX1=(1LL*POWMAX1*POW1)%MOD1;
            POWMAX2=(1LL*POWMAX2*POW2)%MOD2;
        }
        //string
        HS1=(1LL*HS1*POW1 + S[i])%MOD1;
        HS2=(1LL*HS2*POW2 + S[i])%MOD2;
        //
    }
}
void solve(){
    if(HP1==HS1&&HP2==HS2){
        NM++;
        M.push_back(0);
    }
    for(int i=np;i<ns;i++){
        HS1=((HS1 - (S[i-np]*POWMAX1)%MOD1 + MOD1)*POW1 + S[i])%MOD1;
        HS2=((HS2 - (S[i-np]*POWMAX2)%MOD2 + MOD2)*POW2 + S[i])%MOD2;
        if(HP1==HS1&&HP2==HS2){
            NM++;
            if(NM<=1000)
                M.push_back(i-np+1);
        }
    }
    out<<NM<<"\n";
    for(auto x : M){
        out<<x<<" ";
    }
}
int main(){
    read();
    hashes();
    solve();
    return 0;
}