Cod sursă (job #312624)

// Problema sir - lot 2014
// Borcani Robert
// Scor: -- --

#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

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

using VI = vector<int>;
const int mods[2] = { 100003, 500009 };
const int MAXL = 800005;
const int Base = 73;
struct Hash{
    int x[2];

    Hash()
    {
        x[0] = x[1] = 0;
    }
};
string password;
vector<string> words, sqrtw;
vector<Hash> H, passHash;
vector<Hash> powers;
int K, Q;
int sqrtSize;
int cnt;

void ReadWords();       // citesc toate cuvintele, inclusiv parola
void CalcHashPowers();  // calculeaza puterile hash-ului
void makeSqrtParts();   // imi construiesc partile de lungime sqrt
void calcHash( const string& word, Hash& h ); // calculez hash-urile cuvintelor
void getHash( int i1, int i2, Hash& h );    // calculez hash-ul unei parti din parola
void Insert( int pos, char c );              // inserez caracterul c la pozitia pos
bool Query( int pos, int ind );              // fac un query pentru pozitia pos in parola si al ind-lea cuvant
void Degub();           // functie pe care o folosesc sa depanez in timpul scrierii codului

int main()
{
    CalcHashPowers();
    ReadWords();
    makeSqrtParts();
    H = vector<Hash>(words.size());
    for ( int ind = 0; ind < (int)words.size(); ++ind )
        calcHash(words[ind], H[ind]);

    fin >> Q;
    int type, pos, ind, a, b, last{0};
    char c;
    while ( Q-- )
    {
        fin >> type;

        if ( type == 0 )
        {
            fin >> pos >> c >> a >> b;
            if ( last == 0 )
                Insert(pos^a, c);
            else
                Insert(pos^b, c);
        }
        else
        {
            fin >> pos >> ind >> a >> b;
          //  cout << ++cnt << ": ";
            if ( last == 0 )
                fout << (last = Query(pos^a, ind)) << '\n';
            else
                fout << (last = Query(pos^b, ind)) << '\n';
         //   cin.get();
        }
    }

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

void ReadWords()
{
    fin >> password;
    fin >> K;
    string word;
    for ( int i = 0; i < K; ++i )
    {
        fin >> word;
        words.push_back(word);
    }
}

void CalcHashPowers()
{
    powers = vector<Hash>(MAXL);
    powers[0].x[0] = powers[0].x[1] = 1;
    for ( int i = 1; i < MAXL; ++i )
        for ( int j = 0; j < 2; ++j )
            powers[i].x[j] = ( 1LL*powers[i - 1].x[j]*Base ) % mods[j];
}

void makeSqrtParts()
{
    sqrtSize = 1;
    while ( (sqrtSize + 1)*(sqrtSize + 1) <= (int)password.size() )
        ++sqrtSize;

    sqrtw = vector<string>(sqrtSize + 10);
    passHash = vector<Hash>(sqrtSize + 10);
    int ind{0};
    for ( int i = 0; i < (int)password.size(); ++i )
    {
        if ( (int)sqrtw[ind].size() == sqrtSize )
            ++ind;

        sqrtw[ind].push_back(password[i]);
        for ( int j = 0; j < 2; ++j )
            passHash[ind].x[j] = ( 1LL*passHash[ind].x[j]*Base + (int)password[i] ) % mods[j];
    }
}

void calcHash( const string& word, Hash& h )
{
    h.x[0] = h.x[1] = 0;
    for ( int i = 0; i < (int)word.size(); ++i )
        for ( int j = 0; j < 2; ++j )
            h.x[j] = ( 1LL*h.x[j]*Base + (int)word[i] ) % mods[j];
}

void getHash( int i1, int i2, Hash& h )
{
    int currLeft{0}, currRight;
    for ( int ind = 0; ind < (int)sqrtw.size(); ++ind )
    {
        currRight = currLeft + (int)sqrtw[ind].size() - 1;

        if ( currLeft >= i1 && currRight <= i2 )
        {
            for ( int j = 0; j < 2; ++j )
                h.x[j] = ( 1LL*h.x[j]*powers[sqrtw[ind].size()].x[j] + 1LL*passHash[ind].x[j] ) % mods[j];
        }
        else
        {
            int commLeft = max(currLeft, i1), commRight = min(currRight, i2);
            for ( int i = commLeft; i <= commRight; ++i )
                for ( int j = 0; j < 2; ++j )
                    h.x[j] = ( 1LL*h.x[j]*Base + sqrtw[ind][i - currLeft] ) % mods[j];
        }

        currLeft += (int)sqrtw[ind].size();
    }
}

void Insert( int pos, char c )
{
    sqrtSize--;
    --pos;

    for ( int ind = 0; ind < (int)sqrtw.size(); ++ind )
    {
        if ( (int)sqrtw[ind].size() >= pos )
        {
            string s; s.push_back(c);
            sqrtw[ind].insert(pos, s);
            calcHash(sqrtw[ind], passHash[ind]);
            return;
        }
        else
            pos -= (int)sqrtw[ind].size();
    }

    if ( sqrtSize == 0 )
    {
        password = "";

        for ( int i = 0; i < (int)sqrtw.size(); ++i )
            password += sqrtw[i];

        makeSqrtParts();
    }
}

bool Query( int pos, int ind )
{
    Hash h; --pos; --ind;

    getHash(pos - (int)words[ind].size() + 1, pos, h);

    if ( h.x[0] == H[ind].x[0] && h.x[1] == H[ind].x[1] )
        return true;
    return false;
}