Cod sursa(job #1769568)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 2 octombrie 2016 19:15:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.4 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(char c);
    void skipHash(char 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 (x1 % 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(char c)
{
    hashValue = (hashValue * base + c) % mod;
    hashValue = (hashValue%mod + mod) % mod;
}

void RollingHash::skipHash(char c)
{
    hashValue = (hashValue - basePowSize * c) % mod;
    hashValue = (hashValue%mod + mod)%mod;
}

string A,B;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    cin >> A >> B;
    RollingHash hashA(256, 666013, A.size() - 1);
    RollingHash hashAA(256, 100003, A.size() - 1);

    RollingHash hashB(256, 666013, A.size() - 1);
    RollingHash hashBB(256, 100003, A.size() - 1);

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

    vector<int> answer;
    int total = 0;

    for(int i = A.size() - 1; i < B.size(); ++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 - A.size() + 1);
        }
        hashB.skipHash(B[i - A.size() + 1]);
        hashBB.skipHash(B[i - A.size() + 1]);
    }

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

    return 0;
}