Cod sursa(job #1784299)

Utilizator GinguIonutGinguIonut GinguIonut Data 19 octombrie 2016 22:10:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <string.h>
#include <vector>

#define nMax 2000001
#define solMax 1001
#define base 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

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

int lenA, lenB, nrSol;
int Sol[solMax];
char A[nMax], B[nMax];

void read()
{
    fin>>(A+1);
    fin>>(B+1);
    lenA=strlen(A+1);
    lenB=strlen(B+1);
}

void write()
{
    fout<<nrSol<<'\n';
    for(int i=1; i<=min(1000, nrSol); i++)
        fout<<Sol[i]<<" ";
}

void solve()
{
    int hash1A=0, hash2A=0, hash1B=0, hash2B=0, base1=1, base2=1;

    for(int i=1; i<=lenA; i++)
    {
        hash1A=(hash1A*base+A[i])%MOD1;
        hash2A=(hash2A*base+A[i])%MOD2;

        hash1B=(hash1B*base+B[i])%MOD1;
        hash2B=(hash2B*base+B[i])%MOD2;

        if(i>1)
        {
            base1=(base1*base)%MOD1;
            base2=(base2*base)%MOD2;
        }
    }

    if(hash1A==hash1B && hash2A==hash2B)
    {
        nrSol++;
        if(nrSol<solMax)
            Sol[nrSol]=0;
    }

    for(int i=lenA+1; i<=lenB; i++)
    {

        hash1B=((hash1B-(base1*B[i-lenA])%MOD1+MOD1)*base+B[i])%MOD1;
        hash2B=((hash2B-(base2*B[i-lenA])%MOD2+MOD2)*base+B[i])%MOD2;

        if(hash1A==hash1B && hash2A==hash2B)
        {
            nrSol++;

            if(nrSol<solMax)
                Sol[nrSol]=i-lenA;
        }
    }
}

int main()
{
    read();
    solve();
    write();
}