Uva129 Krypton Factor【dfs回溯】【例题7-5】

题目：Krypton Factor

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

思路：

（1）dfs递归枚举前l个字符；

（2）判断相邻的重复子串：无需判断整个串的重复，只需判断当前串的后缀，枚举串的长度（只需枚举到串长的一半），按串长度平分串，然后比较俩串的后缀是否相等。

（3）递归时，找到结果后需要返回值，用于dfs的return结束。

参考：入门经典-例题7-5-P195

代码：

#include <iostream>#include <stdio.h>using namespace std;int n,l,cot,PRt[100];int dfs(int len){    if(cot++ == n){//达到个数        int temp = 0;        for(int i=0;i<len;i++){            printf("%c",prt[i]+'A');            if((i+1)%4 == 0){//4个为一组                if(i+1 >= len) continue;//最后一组不做处理                if((temp+1)%16) printf(" ");                else printf("/n");                temp++;            }        }        if((temp+1)%16 || len%4) printf("/n");//处理最后一个换行        printf("%d/n",len);        return 0;    }    for(int i=0;i<l;i++){//枚举l个字符        prt[len] = i;        int ok = 1;        for(int j=1;j*2<=len+1;j++){//j*2的后缀            int equ = 1;            for(int k=0;k<j;k++){                if(prt[len-k] != prt[len-k-j]){//检查后一半是否等于前一半                    equ = 0;break;                }            }            if(equ){ok = 0;break;}//不相等标记        }        if(ok) if(!dfs(len+1)) return 0;//找到解，返回0，if成立，return结束（如果不加这步的话无法退出递归了）    }return 1;}int main(){    while(scanf("%d%d",&n,&l)!=EOF && (n || l)){        cot = 0;        dfs(0);    }    return 0;}