Word

Dr. R. E. Wright's class was studying modified L-Systems. Let us explain necessary details. As a model let us have words of length n over a two letter alphabet . The words are cyclic, this means we can write one word in any of n forms we receive by cyclic shift, whereby the first and the last letters in the word are considered to be neighbours.

Rewriting rules rewrite a letter at a position i, depending on letters at the positions i - 2, i, i+1. We rewrite all letters of the word in one step. When we have a given starting word and a set of rewriting rules a natural question is: how does the word look after s rewriting steps?

Help Dr. R. E. Wright and write a program which solves this task.

Input 

There are several blocks in the input file, each describing one system. There is an integer number n, 2 < n < 16 the length of the input word in the first line. There is a word in the next line. The word contains only lowercase letters a and b. There are four characters c₁ c₂ c₃ c₄ in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c₁ and the letter at the position i is c₂ and the letter at the position i + 1 is c₃ then the letter at the position i after rewriting will be c₄. Rewriting rules are correct and complete. There is an integer number s, , in the last line of the block.

Output 

There is one line corresponding to each block of the input file. The line contains a word which we receive after s rewriting steps from the corresponding starting word using given rewriting rules. As we mentioned above, the word can be written in any of n cyclic shifted forms. The output file contains the lexicographically smallest word, assuming that a < b.

Sample Input 

5
aaaaa
aaab
aabb
abab
abbb
baab
babb
bbab
bbbb
1

Sample Output 

bbbbb

---

題目描述：

字串是一個環狀的, 每次會藉由規則轉換成另一個字串, 問轉換 s 次之後的字串為何。
並且以環狀最小表示法輸出結果。

題目解法：

尋找環的長度, 以及一開始多餘的長度。

中間用了 周源 最小表示法。


#include <stdio.h>
#include <map>
#include <iostream>
using namespace std;
int MinExp(const char *s, const int slen) {
    int i = 0, j = 1, k = 0, x, y, tmp;
    while(i < slen && j < slen && k < slen) {
        x = i + k;
        y = j + k;
        if(x >= slen)    x -= slen;
        if(y >= slen)    y -= slen;
        if(s[x] == s[y]) {
            k++;
        } else if(s[x] > s[y]) {
            i = j+1 > i+k+1 ? j+1 : i+k+1;
            k = 0;
            tmp = i, i = j, j = tmp;
        } else {
            j = i+1 > j+k+1 ? i+1 : j+k+1;
            k = 0;
        }
    }
    return i;
}
string makeMinExp(const char *s, const int n) {
    int pos = MinExp(s, n), i;
    string ss = "";
    for(i = pos; i < n; i++)
        ss += s[i];
    for(i = 0; i < pos; i++)
        ss += s[i];
    return ss;
}
int main() {
    int n, m, i, j, k, rank;
    char s[105], rule[8][10];
    int nrule[8];
    while(scanf("%d", &n) == 1) {
        scanf("%s", s);
        for(i = 0; i < 8; i++) {
            scanf("%s", rule[i]);
            m = (rule[i][0]-'a')|((rule[i][1]-'a')<<1)|((rule[i][2]-'a')<<2);
            nrule[m] = rule[i][3];
        }
        scanf("%d", &rank);
        string ss = makeMinExp(s, n);
        map<string, int> R;
        int tail, length, idx = 0;
        do {
            if(R.find(ss) != R.end()) {
                tail = R[ss], length = idx - tail;
                break;
            }
            R[ss] = idx, idx++;
            for(i = 0; i < n; i++) {
                m = (ss[(i-2+n)%n]-'a')|((ss[i]-'a')<<1)|((ss[(i+1)%n]-'a')<<2);
                s[i] = nrule[m];
            }
            ss = makeMinExp(s, n);
        } while(true);
        if(rank >= tail) {
            idx = (rank-tail)%length + tail;
        } else  idx = rank;
        for(map<string, int>::iterator it = R.begin();
            it != R.end(); it++) {
            if(it->second == idx) {
                cout << it->first << endl;
                break;
            }
        }
    }
    return 0;
}