Cod sursa(job #2391102)

Utilizator StormieStormie Stormie Data 28 martie 2019 17:43:59
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
#define MAXIM 2000010
#define d 256
#define q 100007


using namespace std;

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

char A[MAXIM], B[MAXIM];
int hashA, hashB, power = 1, nrSol;
vector <int> G;

int main()
{
    f >> A >> B;

    for(unsigned int i = 0; i < strlen(A); i++)
    {
        hashA = (hashA * d + A[i]) % q;
        hashB = (hashB * d + B[i]) % q;

        if(i) power = (power * d) % q;
    }

    //cout << hashA << '\n';

    for(unsigned int i = 0; i <= strlen(B) - strlen(A); i++)
    {
       // cout << hashB << '\n';
        if(hashA == hashB)
        {
            int ok = 1;
            for(unsigned int j = 0; j < strlen(A) && ok; j++)
                if(A[j] != B[i + j]) ok = 0;
            nrSol++;
            if(nrSol < 999) G.push_back(i);
        }

        if(i != strlen(B) - strlen(A))
        {
            //cout << B[i] << ' ' << B[i + strlen(A)] << '\n';
            hashB = ((hashB - B[i] * power) % q * d + B[i + strlen(A)]) % q;
            if(hashB < 0) hashB = q + hashB;
        }

    }

    g << nrSol << '\n';
    for(unsigned int i = 0; i < G.size(); i++)
        g << G[i] << ' ';

    f.close();
    g.close();

    return 0;
}