【题解】UVa 129【Krypton Factor】

分析

从左到右依次考虑每个位置上的字符,只需要判断当前串的后缀,而非所有子串。

代码

#include<cstdio>

const int MAXN = 666;
int n,L,cnt,S[MAXN];//cnt记录已经生成的合法字符串个数 

int dfs(int cur){//cur记录S此时对应的字符串长度 
    if(cnt++ == n){//完成搜索,输出结果并逐级返回0 
        for(int i = 0;i < cur;i++){//特定格式输出 
            if(i % 64 == 0 && i) printf("\n");
            else if(i % 4 == 0 && i) printf(" ");
            printf("%c",'A' + S[i]);
        }
        printf("\n%d\n",cur);
        return 0;
    }
    for(int i = 0;i < L;i++){//i从0开始,'A' + S[cur]从A开始 
        S[cur] = i;
        bool ok = true;
        for(int j = 1;j * 2 <= cur + 1;j++){//从j为1开始检查所有含有尾字母的相邻子串是否满足条件 
            bool equal = true;
            for(int k = 0;k < j;k++){
                if(S[cur - k] != S[cur - k - j]){equal = false;break;}
            }
            if(equal){ok = false;break;}
        }
        if(ok) if(!dfs(cur + 1)) return 0;
    }
    return 1;
}

int main(){
    while(scanf("%d %d",&n,&L) == 2 && n){
        cnt = 0;
        dfs(0);
    }

    return 0;
}