2013-06-26 14:31:31Morris
[UVA] 517 - Word
Word
| 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 c1 c2 c3 c4 in the next eight lines. Each quadruple represents one rewriting rule with the following meaning: when the letter at the position i - 2 is c1 and the letter at the position i is c2 and the letter at the position i + 1 is c3 then the letter at the position i after rewriting will be c4. 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;
}