Решение задачи Марковский цикл с Меньшиков

#include <iostream>
#include <cstdio>
#include <string>
#include <set>
#include <vector>
#include <map>
 
using namespace std;
const int osn = 3;
int calcHash(const string &str)
{
    int hash = 0;
    for (int i=0;i<str.size();i++) {
        hash = hash * osn + str[i] -'A';
    }
    return hash;
}
struct rule
{
    string L;
    string R;
    int hash;
    rule(){}
    rule(string left, string right)
    {
        L = left;
        R = right;
        hash = calcHash(left);
    }
};
struct entry
{
    int H;
    int P;
    entry(){H = 0; P = 0;}
    entry(int hash, int pos)
    {
        H = hash;
        P = pos;
    }
};
bool operator < (const entry &a, const entry &b)
{
    return a.H < b.H;
}
vector<rule> rules;
string str;
void trim(string &str)
{
    while (str[0] == ' ')
        str.erase(0,1);
 
    while (str[str.size() - 1] == ' ')
        str.erase(str.size()-1, 1);
}
void input()
{
    getline(cin, str);
    trim(str);
    string buf,left,right;
    while(getline(cin,buf)) {
        int pos = buf.find('-');
        left = buf.substr(0,pos);
        right = buf.substr(pos+2,buf.size() - (pos+2));
        trim(left); trim(right);
        rules.push_back(rule(left,right));
    }
}
typedef set<entry> S_ENT;
vector<int> step;
vector<S_ENT > sizeHash;
vector<int> curHash;
void recalcSizeHash()
{
    for (int i=0;i<sizeHash.size();i++)
        sizeHash[i].clear();
    curHash.assign(curHash.size(), 0);
 
    for (int i=0; i<=str.size();i++)
    {
        int c = i == str.size() ? 0 :str[i] - 'A';
        for (int j=0; j < curHash.size(); j++)
        {
            if (i <= j)
                curHash[j] = curHash[j] * osn + c;
            else {
                entry curEntry(curHash[j],i-1-j);
 
                if (sizeHash[j].find(curEntry) == sizeHash[j].end())
                    sizeHash[j].insert(curEntry);
 
                curHash[j] = (curHash[j] % step[j]) * osn + c;
            }
        }
    }
}
vector<int> mem(531442,-1);
void solve()
{
    step.resize(str.size());
    step[0] = 1;
    for (int i=1;i<step.size();i++)
        step[i] = step[i-1] * osn;
    sizeHash.resize(str.size());
    curHash.resize(str.size(),0);
   
    bool isOK;
    int stepAmount = 0;
    int perLen = 0;
    do
    {
        int memPos = calcHash(str);
        if (mem[memPos] != -1) {
            perLen = stepAmount - mem[memPos];
            stepAmount = mem[memPos] + 1;
            break;
        }
        else
            mem[memPos] = stepAmount++;
 
        isOK = false;
        recalcSizeHash();
        int len;
        entry curE;
        S_ENT::iterator it;
        for (int i=0;i<rules.size();i++)
        {
            len = rules[i].L.size() - 1;
            curE.H = rules[i].hash;
            if (len < sizeHash.size()) {
                it  = sizeHash[len].find(curE);
                if (it != sizeHash[len].end())
                {
                    int pos = 0;
                    for (int j = it->P; pos<len+1; j++)
                        str[j] = rules[i].R[pos++];
                    isOK = true;
                    break;
                }
            }
        }
    }
    while (isOK);
 
    cout<<stepAmount - 1<<' '<<perLen;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    return 0;
}