題目：Krypton Factor

題意：如果一個(gè)字符串包含兩個(gè)相鄰的重復(fù)子串，則稱它是“容易的串”，其他串稱為“困難的串”。輸入n，L，輸出由前L個(gè)字符組成的、 字典序第n小的困難的串。

思路：

（1）dfs遞歸枚舉前l(fā)個(gè)字符；

（2）判斷相鄰的重復(fù)子串：無(wú)需判斷整個(gè)串的重復(fù)，只需判斷當(dāng)前串的后綴，枚舉串的長(zhǎng)度（只需枚舉到串長(zhǎng)的一半），按串長(zhǎng)度平分串，然后比較倆串的后綴是否相等。

（3）遞歸時(shí)，找到結(jié)果后需要返回值，用于dfs的return結(jié)束。

參考：入門(mén)經(jīng)典-例題7-5-P195

代碼：

#include <iostream>#include <stdio.h>using namespace std;int n,l,cot,PRt[100];int dfs(int len){    if(cot++ == n){//達(dá)到個(gè)數(shù)        int temp = 0;        for(int i=0;i<len;i++){            printf("%c",prt[i]+'A');            if((i+1)%4 == 0){//4個(gè)為一組                if(i+1 >= len) continue;//最后一組不做處理                if((temp+1)%16) printf(" ");                else printf("/n");                temp++;            }        }        if((temp+1)%16 || len%4) printf("/n");//處理最后一個(gè)換行        printf("%d/n",len);        return 0;    }    for(int i=0;i<l;i++){//枚舉l個(gè)字符        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;}//不相等標(biāo)記        }        if(ok) if(!dfs(len+1)) return 0;//找到解，返回0，if成立，return結(jié)束（如果不加這步的話無(wú)法退出遞歸了）    }return 1;}int main(){    while(scanf("%d%d",&n,&l)!=EOF && (n || l)){        cot = 0;        dfs(0);    }    return 0;}