Cod sursa(job #2426470)

Utilizator PetrescuAlexandru Petrescu Petrescu Data 28 mai 2019 11:03:06
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.55 kb
#include <fstream>
#include <iostream>
#define HASH_BASE 71
#define MODULO1 100007
#define MODULO2 100021
#define MAX 1001

using namespace std;

typedef long long LL;
int position[MAX];

LL hashFunction1(string a)
{
    int n = a.length(), i, hashBase = HASH_BASE;
    LL hashValue = 0;

    for(i = 0; i < n; i++)hashValue = (hashValue * hashBase + a[i]) % MODULO1;

    return hashValue;
}

LL hashFunction2(string a)
{
    int n = a.length(), i, hashBase = HASH_BASE;
    LL hashValue = 0;

    for(i = 0; i < n; i++)hashValue = (hashValue * hashBase + a[i]) % MODULO2;

    return hashValue;
}

LL ridicare1(int baza, int exponent)
{
    int putere = 1;

    while(exponent > 0)
    {
        if(exponent % 2 == 1)putere = putere * baza % MODULO1;

        baza = baza * baza % MODULO1;

        exponent /= 2;
    }

    return putere;
}

LL ridicare2(int baza, int exponent)
{
    int putere = 1;

    while(exponent > 0)
    {
        if(exponent % 2 == 1)putere = putere * baza % MODULO2;

        baza = baza * baza % MODULO2;

        exponent /= 2;
    }

    return putere;
}

int solve(string a, string b)
{
    LL hashValueA1, hashValueA2, hashValueC1, hashValueC2;
    int n = a.length(), m = b.length(), contor = 0, i;
    string c;

    hashValueA1 = hashFunction1(a);
    hashValueA2 = hashFunction2(a);

    c = "";

    for(i = 0; i < n; i++)c = c + b[i];

    hashValueC1 = hashFunction1(c);
    hashValueC2 = hashFunction2(c);

    if(hashValueA1 == hashValueC1 && hashValueA2 == hashValueC2)
    {
        contor++;
        if(contor < MAX)position[contor] = 0;
    }

    for(i = 1; i < m - n + 1; i++)
    {
        hashValueC1 = (hashValueC1 - b[i - 1] * ridicare1(HASH_BASE, n - 1) % MODULO1) * HASH_BASE % MODULO1 + b[i + n - 1];
        hashValueC2 = (hashValueC2 - b[i - 1] * ridicare2(HASH_BASE, n - 1) % MODULO2) * HASH_BASE % MODULO2 + b[i + n - 1];
       // cout << hashValueA1 << " " << hashValueC1 << " " << hashValueA2 << " " << hashValueC2 << " " << endl;

        if(hashValueA1 == hashValueC1 && hashValueA2 == hashValueC2)
        {
            contor++;
            if(contor < MAX)position[contor] = i;
        }
    }

    return contor;
}

int main()
{
    int i, contor;
    string a, b;

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

    fin >> a >> b;

    contor = solve(a, b);
    fout << contor << '\n';

    for(i = 1; i <= min(contor, MAX - 1); i++)fout << position[i] << " ";

    fin.close();
    fout.close();
}