Uva 129 困难串好难啊

一、题意

如果一个字符串包含两个相邻的重复子串，则称它为容易的串。
输入k和L, 要求输出由前L个字母组成的、字典序第k小的困难的串。

二、解析

通过回溯法按字典序枚举字符串，每次枚举都对应这当前字符串的最后一个字符。因此判断是否是困难的串时，就可以只判断当前字符串的后缀有没有出现相邻的重复子串即可。
这个原理就像是：八皇后问题中，只需要判断新皇后和之前的皇后有无冲突，而不需要判断以前的皇后是否相互冲突。

三、代码

#include <iostream>
#include <string>
using namespace std;
int k, L, cnt;
string ans;
bool ok = 0;

void output(int idx) {
    int cnt = 0;
    for(int i = 0; i <= idx; i ++) {
        if(i && i % 4 == 0) {
            cnt ++;
            if(cnt % 16) cout << " ";
            else cout << "\n";
        }
        cout << ans[i];
    }
    cout << "\n" << idx + 1 << endl;
}

bool isOK(int n) {
    for(int len = 1; len * 2 <= n; len ++) {
        if(ans.substr(n - len, len) == ans.substr(n - 2 * len, len)) return 0;
    }
    return 1;
}

void solve(int idx, char cur) {
    if(idx < ans.size()) ans[idx] = cur;
    else ans += cur;
    if(!isOK(idx + 1)) return;

    cnt ++;
    if(cnt == k) {
        ok = 1, output(idx);
        return;
    }
    for(int i = 0; !ok && i < L; i ++) solve(idx + 1, 'A' + i);
}

int main() {
    while(cin >> k >> L && k) {
        ok = 0, cnt = 0;
        ans.clear();
        for(int i = 0; i < L; i ++) solve(0, 'A' + i);
    }
}

四、归纳

• 当需要按照字典序枚举字符串时，优先考虑回溯法
• 当需要维护一个字符串时，即可以考虑用char数组，也可以考虑用string, 这一题我用的string，因为string判断困难串代码量比较少。