题目大意：
给出n，l；要求按特定格式输出由前l个大写字母构成的按字母表排列的第n个没有连续重复子串的字符串以及该字符串长度。
此题是一道dfs递归回溯的基础题，难点在于对当前字符串是否有连续重复子串的判断，具体做法是这样的，以长度为对象枚举以新添进字符为尾巴的子串，看是否重复。
但是我还是有一点疑问，为什么我将这段代码做出下列改动，就会Runtime error!
#include <cstdio> int S[100]; int n, L, cnt;//cnt记录已经生成的合法字符串的个数 int dfs(int cur)//cur记录S此时对应的字符串的长度 //改成void dfs(int cur) { if (cnt++ == n)//完成搜索，输出结果并逐级结束函数调用 (返回0） { for (int i = 0; i < cur; ++i) { if (i % 64 == 0 && i) printf(" "); //注意这里要将i%64放在i%4的前面，优先换行 else if (i % 4 == 0 && i) printf(" "); //这里要用else if，防止输出下一行的时候，同时第一个位置为空格 printf("%c", 'A' + S[i]); }//特定格式输出 printf(" %d ", cur); return 0;//函数调用结束 //改成return; } for (int i = 0; i < L; ++i)//i从0开始，'A'+s[cur]从A开始 { S[cur] = i; int ok = 1; for (int j = 1; j * 2 <= cur + 1; ++j)//以长度为对象枚举以新添进字符为尾巴的子串，看是否重复。 { int equal = 1; for (int k = 0; k < j; ++k) if (S[cur - k] != S[cur - k - j]) { equal = 0; break; } //以j为长度枚举的相邻字串中，只要有任意一个字符与它对应位置的字符不相等，那么，以当前长度枚举的相邻子串就不相等 if (equal) { ok = 0; break; } } if (ok) if (!dfs(cur + 1)) return 0; //将这里改成if(ok)dfs(cur+1); } return 1; //将这里删去 } int main() { while (scanf("%d%d", &n, &L) == 2, n || L) { cnt = 0;//已找到合法字符串0个 dfs(0);//开始时S数组对应的字符串长度为0 } return 0; }
2018-04-14