題目：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;}