UVA – 129 Krypton Factor （困难的串）（回溯法）

题意：求由字母表前L个字母组成的字典序第n小的困难串。（如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。）

分析：回溯时，检查枚举的当前串是否为困难串的方法：将最后一个字母（下标为cur）与第cur-j个字母不断依次向前比较j个字母。

采用此种方法的原因是，前面的串都已经是回文串。

例如：ABAC，不需检查每个长度为偶数的串是否符合要求，因为枚举的每一步都保证是困难串，所以长度为2的串只需检查AC，无需检查AB，BA。

#pragma comment(linker, "/STACK:102400000, 102400000")
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
#define Min(a, b) ((a < b) ? a : b)
#define Max(a, b) ((a < b) ? b : a)
typedef long long ll;
typedef unsigned long long llu;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {, , -, , -, -, , };
const int dc[] = {-, , , , -, , -, };
const int MOD = 1e9 + ;
const double pi = acos(-1.0);
const double eps = 1e-;
const int MAXN =  + ;
const int MAXT =  + ;
using namespace std;
int n, L;
int ans[MAXN];
int cnt;
int dfs(int cur){
    if(cnt++ == n){//cnt为当前为第几串
        for(int i = ; i < cur; ++i){
            if(i && (i %  == )) printf("\n");
            else if(i && (i %  == )) printf(" ");
            printf("%c", 'A' + ans[i]);
        }
        printf("\n");
        printf("%d\n", cur);
        return ;
    }
    else{
        for(int i = ; i < L; ++i){
            ans[cur] = i;
            bool ok = true;
            for(int j = ; j *  <= cur + ; ++j){//cur+1为当前串的长度,检查后缀最多只用检查到（cur+1）/2,因为再往前检查，检查的前串短于后串，没必要检查
                bool flag = true;
                for(int k = ; k < j; ++k){
                    if(ans[cur - k] != ans[cur - k - j]){
                        flag = false;
                        break;
                    }
                }
                if(flag){//方案不合法
                    ok = false;
                    break;
                }
            }
            if(ok){//方案合法继续递归
                if(!dfs(cur + )) return ;//已经找到解，退出所有递归
            }
        }
        return ;
    }
}
int main(){
    while(scanf("%d%d", &n, &L) == ){
        if(!n && !L) return ;
        cnt = ;
        memset(ans, , sizeof ans);
        dfs();
    }
    return ;
}