Cod sursa(job #2196525)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 19 aprilie 2018 17:32:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <cctype>

#define MOD1 666013
#define MOD2 10013
#define BAZA1 127
#define BAZA2 131

using namespace std;

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

char A[2000005];
char B[2000005];

long long n, m;
int i,j;

long long h1, h2;
long long h11, h22;
long long putere1, putere2;

vector <long long> SOL;

long long lgput (long long n, long long p, long long mod)
{
    long long sol=1;
    long long aux=n;

    int i;

    for(i=0; (1<<i)<=p; ++i) {
        if((p&(1<<i))!=0)
            sol=(sol*aux)%mod;

        aux=(aux*aux)%mod;
    }

    return sol;
}

int main()
{
    f.getline(A, 2000002);
    f.getline(B, 2000002);

    n=strlen(A);
    m=strlen(B);

    h1=h2=0;
    h11=h22=0;

    for(i=0; i<n; i++) {
        h1=(h1*BAZA1%MOD1 + (A[i]-'0'))%MOD1;
        h2=(h2*BAZA2%MOD2 + (A[i]-'0'))%MOD2;

        h11=(h11*BAZA1%MOD1 + (B[i]-'0'))%MOD1;
        h22=(h22*BAZA2%MOD2 + (B[i]-'0'))%MOD2;
    }

    putere1=lgput(BAZA1, n-1, MOD1);
    putere2=lgput(BAZA2, n-1, MOD2);

    if(h1==h11 && h2==h22)
        SOL.push_back(0);

    for(i=n; i<m; i++) {
        h11=((h11-((B[i-n]-'0')*putere1)%MOD1+MOD1)*BAZA1+(B[i]-'0'))%MOD1;

        h22=((h22-((B[i-n]-'0')*putere2)%MOD2+MOD2)*BAZA2+(B[i]-'0'))%MOD2;

        if(h1==h11 && h2==h22)
            SOL.push_back(i-n+1);
    }

    g<<SOL.size()<<'\n';

    for(i=0; i<1000 && i<SOL.size(); i++)
        g<<SOL[i]<<' ';

    g<<'\n';

    return 0;
}