/* explanation: m=3 n=3 characters: ['0','1','2'] growing chain: 012 0120 -> after "2", next character is "0" 01201 -> next character is "1" 012010 -> 012 would be a repeated 3-pattern, character after "2" is "0" 0120101 -> next character is "1" 01201011 -> 012 repeats, 010 repeats, 011 ok 012010112 -> next character is "2" 0120101121 -> 120 repeats, 121 ok 01201011212 -> next character is "1" 012010112122 -> 120 repeats, 121 repeats, 122 ok 0120101121220 -> next character is "0" 01201011212202 -> 201 repeats, 202 ok 012010112122020 -> next character is "0" 0120101121220200 -> 201 repeats, 202 repeats, 200 ok 01201011212202001 -> next character is "1" 012 -> repeats 010 -> repeats 011 -> repeats chain is broken chain.length = 17 output: 17 some cases: 2,2 => 4 13,1 => 13 5,7 => 107 7,4 => 136 42,42 => 69824 90,19 => 144288 1000000,6 => 4999992250005 Input checking not done. Enter two integers either space separated or on separate lines. 1st no represents, number of unique chars 2nd no represents length of pattern. */ #include #include #include #include #include using namespace std; using pMap = map; int main() { // unique chars in the chain int numchars{3}; cin >> numchars; // pattern length to match int patlen{3}; cin >> patlen; // chain of non-repeated chars string chain(numchars + patlen - 1, ' '); // generate initial sequence generate(begin(chain), end(chain), [ i = 0, numchars ]() mutable { return i++ % numchars + 48; }); pMap pmap; // holds patterns to match // put the initial patterns to match, // each pattern to match have length // patlen for (auto i{0}; i < numchars; ++i) pmap.emplace(chain.substr(i, patlen), 1); // running char count int pnxt{(numchars + patlen) % numchars}; string pat{chain.substr(0, numchars)}; // work string to form a pattern of // length patlen string wpat = chain.substr(numchars); for (int idx{0}; idx < numchars; pnxt++) { char ch{pat.at(pnxt % numchars)}; wpat += ch; // check if current pattern // already exist if (pmap[wpat] == 0) { // no so add it. pmap[wpat]++; // append to our chain chain += ch; // update the working pattern wpat = wpat.substr(1); idx = 0; } else { // no match, update working // pattern by removing the // last added char and update // the try count. wpat.pop_back(); idx += 1; } // end else of } // end for cout << "sequence = " << chain << '\n' << "length = " << chain.size() << '\n'; }

broken_chain.cpp