• 題目:
  • • 分析與解答：

題目:

如果一個(gè)字符串包含兩個(gè)相鄰的重復(fù)子串，則稱它是“容易的串”，其他串成為“困難的串”。例如:BB,ABCDACABCAB,ABCDABCD都是容易的，而D、DC、ABDAB、CBABCBA
都是困難的。
輸入正整數(shù)n和L，輸出由前L個(gè)字符組成的、字典序第n個(gè)小的困難的串。例如，當(dāng)L=3時(shí)，前7個(gè)困難的串分別為:A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。
輸入保證答案不超過80個(gè)字符
輸入:
7 3
30 3
輸出:
ABACA BA
ABACA BCACB ABCAB ACABC ACBAC ABA

分析與解答：

在回溯算法中，應(yīng)注意避免不必要的判斷，八皇后問題中，只需判斷新皇后和之前的皇后是否沖突，而不必判斷以前的皇后是否相互沖突。
這一題只需判斷當(dāng)前串的偶數(shù)項(xiàng)后綴是否對(duì)稱

BB,長度為1*2的后綴對(duì)稱
ABCDACABCAB,長度為3*2的后綴對(duì)稱
ABCDABCD長度為4*2的后綴對(duì)稱

像這些對(duì)稱的串，必定不為困難的串

#include<stdio.h> #include<string.h> #define MAX 90 int S[MAX]; //保存第i個(gè)位置應(yīng)該放哪個(gè)字符 int n,L; int dfs(int cur) //返回0表示已經(jīng)得到解 { int i,j,k;if(cur == n){for(i=0;i<cur;i++){printf("%c",'A'+S[i]);}printf("\n");return 0;}for(i=0;i<L;i++){int ok=1; //判斷方案是否合法S[cur]=i; //將當(dāng)前位置設(shè)定為i“0==A，1==B，2==C”for(j=1;2*j<=cur+1;j++) //循環(huán)判斷長度長度為j*2的后綴{int equal=1; //判斷后綴中是否有前一半是否等于后一半for(k=0;k<j;k++){if(S[cur-k]!=S[cur-k-j]) //只要確定了后綴j*2中有一個(gè)不相等，則可以確定前一半與后一半不相等{equal=0;break;}}if(equal)//前一半等于后一半，方案不合法 {ok=0;break;}}if(ok){if(!dfs(cur+1)) //到這里，說明0到cur位置的困難串已經(jīng)確立好了，確立下一個(gè)位置就好//如果已經(jīng)找出字典序第n小的串，那么dfs（cur+1）返回0，此時(shí)直接退出 return 0;}}return 1; } int main() {while(scanf("%d%d",&n,&L)!=EOF){memset(S,0,sizeof(S));dfs(0);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的（回溯 UVa129）困难的串的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。