Cod sursa(job #2299086)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 8 decembrie 2018 21:18:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

const int B1=131, M1=666013;
const int B2=127, M2=10013;

const int NMAX=2e6+5;

char A[NMAX], B[NMAX];
int N, M;

long long R1, R11, R2, R22, pow1=1, pow2=1;

int Sol[NMAX], vf;

int i;

int main()
{
    f.tie(NULL);

    f>>A>>B;

    N=(int)strlen(A);
    M=(int)strlen(B);

    for(i=0; i<N; ++i)
    {
        R1=R1*B1%M1+(A[i]-'0');
        R1%=M1;
        R2=R2*B2%M2+(A[i]-'0');
        R2%=M2;

        R11=R11*B1%M1+(B[i]-'0');
        R11%=M1;
        R22=R22*B2%M2+(B[i]-'0');
        R22%=M2;
    }

    //R1, R2 - codificari initiale;

    for(i=1; i<N; ++i)
    {
        pow1*=B1;
        pow1%=M1;

        pow2*=B2;
        pow2%=M2;
    }

    if(R1 == R11 && R2 == R22)
        Sol[++vf]=0;

    for(i=N; i<M; ++i)
    {
        R11=R11-((B[i-N]-'0')*pow1%M1);
        R11+=M1;
        R11*=B1;
        R11+=(B[i]-'0');
        R11%=M1;

        R22=R22-((B[i-N]-'0')*pow2%M2);
        R22+=M2;
        R22*=B2;
        R22+=(B[i]-'0');
        R22%=M2;

        if(R1 == R11 && R2 == R22)
            Sol[++vf]=i-N+1;
    }

    g<<vf<<'\n';

    for(i=1; i<=min(vf, 1000); ++i)
        g<<Sol[i]<<' ';

    g<<'\n';

    return 0;
}