Paste will expire never.
- // Меньшиков. Тренировка 14.
- // 14A. Марковский цикл [markovc]
- // ibelyaev: 09Jan2011
- #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;
- }
Editing is locked.