Cod sursa(job #1713008)

Utilizator S7012MYPetru Trimbitas S7012MY Data 4 iunie 2016 14:47:41
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define MOD 666013
#define MOD2 100007
#define BASE 31
using namespace std;

string a,b;
int A,B,put=1,putp=1,nrs;
int Ap,Bp;
vector<int> sol;

int hs(string a,int md) {
    int A=0;
    for(int i=0; i<a.size(); ++i) A=(A*BASE+a[i])%md;
    return A;
}

int main()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");
    f>>a>>b;
    int sz=a.size();
    A=hs(a,MOD);
    Ap=hs(a,MOD2);
    for(int i=0; i<sz; ++i) {
        B=(B*BASE+b[i])%MOD;
        Bp=(Bp*BASE+b[i])%MOD2;
        if(i) {
            put=(put*BASE)%MOD;
            putp=(putp*BASE)%MOD2;
        }
    }
    for(int i=sz; i<b.size(); ++i) {
        B=(B-b[i-sz]*put)%MOD+MOD;
        B=(B*BASE+b[i])%MOD;
        Bp=(Bp-b[i-sz]*putp)%MOD2+MOD2;
        Bp=(Bp*BASE+b[i])%MOD2;
        //cout<<A<<' '<<Ap<<' '<<B<<' '<<Bp<<'\n';
        if(B==A && Bp==Ap) {
          ++nrs;
          if(sol.size()<1000) sol.push_back(i);
        }
    }
    g<<nrs<<'\n';
    for(int i=0; i<sol.size();++i) g<<sol[i]-sz+1<<' ';
    return 0;
}