Cod sursa(job #2198361)

Utilizator RaduVFVintila Radu-Florian RaduVF Data 24 aprilie 2018 12:41:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define nmax 2000005
#define MOD1 666013
#define MOD2 123451
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int baza = 256;
vector <int> sol;
string A, B;
int hashA1, hashA2, P1=1, P2=1;
int hashB1, hashB2;
int contor;

int main()
{
    fin>>A>>B;
    int NA=(int)A.size(), NB=(int)B.size();
    if(NA > NB) {
        fout<<0;
        return 0;
    }
    for(int i=0; i<NA; ++i) {
        hashA1=(hashA1*baza+A[i])%MOD1;
        hashA2=(hashA2*baza+A[i])%MOD2;
        if(i) {
            P1=(P1*baza)%MOD1;
            P2=(P2*baza)%MOD2;
        }
       // cout<<hashA1<<' '<<hashA2<<' '<<P1<<' '<<P2<<endl;
    }
    for(int i=0; i<NA; ++i)
        hashB1=(hashB1*baza+B[i])%MOD1,
        hashB2=(hashB2*baza+B[i])%MOD2;
    if(hashA1 == hashB1 && hashA2 == hashB2) {
        ++contor;
        sol.push_back(0);
    }
    for(int i=NA; i<=NB; ++i) {
        hashB1=((hashB1+MOD1-(B[i-NA]*P1)%MOD1)*baza+B[i])%MOD1;
        hashB2=((hashB2+MOD2-(B[i-NA]*P2)%MOD2)*baza+B[i])%MOD2;
       // cout<<hashB1<<' '<<hashB2<<endl;
        if(hashB1==hashA1 && hashB2==hashA2) {
            ++contor;
            if(contor<=1000) {
                sol.push_back(i-NA+1);
            }
        }
    }
    fout<<contor<<endl;
    for(unsigned i=0; i<sol.size(); ++i) {
        fout<<sol[i]<<' ';
    }
    return 0;
}