Cod sursa(job #1769600)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 octombrie 2016 20:00:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#include <bits/stdc++.h>

using namespace std;

class RollingHash{
private:
    int hashValue = 0;
    int size = 0;
    int basePowSize = 0;
    int base = 0;
    int mod = 0;
    int lgPowerRaise(int x,int y, int mod);
public:
    RollingHash(int _base, int _mod, int _size);
    int getHash();
    void appendHash(int c);
    void skipHash(int c);
};

int RollingHash::lgPowerRaise(int x, int y, int mod)
{
    long long x1 = x,x2 = 1;
    if(y == 0)
        return 1;
    if(y == 1)
        return x % mod;
    while (y)
        if (y & 1) {
            y ^= 1;
            x2 = (x1 * x2) % mod;
        }
        else {
            y >>= 1;
            x1 = (x1 * x1) % mod;
        }
    return (x2 % mod + mod ) % mod;
}

RollingHash::RollingHash(int _base, int _mod, int _size)
{
    hashValue = 0;
    base = _base;
    mod = _mod;
    size = _size;
    basePowSize = lgPowerRaise(base, size, mod);
}

int RollingHash::getHash()
{
    return hashValue;
}

void RollingHash::appendHash(int c)
{
    hashValue = (hashValue * base + c) % mod;
}

void RollingHash::skipHash(int c)
{
    hashValue = (hashValue - basePowSize * c) % mod;
    hashValue = (hashValue + mod) % mod;
}
const int Nmax = 2000005;
char A[Nmax],B[Nmax];
int N,M;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",&A,&B);

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

    RollingHash hashA(256, 666013, N - 1);
    RollingHash hashAA(256, 100003, N - 1);

    RollingHash hashB(256, 666013, N - 1);
    RollingHash hashBB(256, 100003, N - 1);

    for (int i = 0; i < N; ++i) {
        hashA.appendHash(A[i]);
        hashAA.appendHash(A[i]);
    }
    for (int i = 0; i < N - 1; ++i) {
        hashB.appendHash(B[i]);
        hashBB.appendHash(B[i]);
    }

    vector<int> answer;
    int total = 0;

    for(int i = N - 1; i < M; ++i)
    {
        hashB.appendHash(B[i]);
        hashBB.appendHash(B[i]);
        if (hashA.getHash() == hashB.getHash() &&
            hashAA.getHash() == hashBB.getHash()) {
            ++total;
            if(total <= 1000)
                answer.push_back(i - N + 1);
        }
        hashB.skipHash(B[i - N + 1]);
        hashBB.skipHash(B[i - N + 1]);
    }

    cout << total << "\n";
    for(auto it : answer)
        cout << it << " ";

    return 0;
}