Cod sursa(job #1950552)

Utilizator RaZxKiDDavid Razvan RaZxKiD Data 3 aprilie 2017 09:48:23
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>

using namespace std;

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

string P,S;
int np,ns;
int NM;
bitset<2000005> SM;

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(np>ns){
        out<<0;
        return;
    }
    if(HP1==HS1&&HP2==HS2){
        NM++;
        SM[0]=1;
    }
    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)
                SM[i-np+1]=1;
        }
    }
    out<<NM<<"\n";
    NM=0;
    for(int i=0;i<ns&&NM<=1000;i++){
        if(SM[i]){
            out<<i<<" ";
            NM++;
        }
    }
}
int main(){
    read();
    hashes();
    solve();
    return 0;
}