题目描述：
果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。例如，
BB、ABCDABCD都是容易的串，而D、DC、ABDAD、CBABCBA都是困难的串。
输入正整数n和L，输出由前L个字符组成的、字典序第n个困难的串。例如，当L=3时，前7个困难的串分别为A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。输入保证答案不超过80个字符。
题目思路：
- 这道题从题目要求入手，看到困难的串的定义，可以想到：在组合成下一个串之前，先检查当前从A开始哪一个字母可以跟前缀构成困难的串。
- 我们需要假设在执行当前检查的时候，前面组成的串都是困难的串，迭代时只需向后检查，不需要检查前面的。
代码：
#include<iostream> #include<string> using namespace std; //维持字典序：能深着走绝不横着走，先不考虑平行状态 int cnt = 0; //可以画图理解以下代码，主要代码为dfs部分 bool isHard(string prefix, char i){ int width = 1, count = 0; for(int j = prefix.length()-1; j >= 0; j -= 2){ const string s1 = prefix.substr(j,width); const string s2 = prefix.substr(j+count+1)+i; // cout << endl << "prefix:" << prefix << "\ti:" << i << "\ts1:" << s1 << "\ts2:" << s2 << "\ts1.compare(s2):" << s1.compare(s2) << endl << endl; if(s1.compare(s2) == 0) return false; width++; count++; } return true; } void dfs(int l, int n, string prefix){ for(char i = 'A'; i < 'A'+l; i++){ //从第一个字母开始往后 if(isHard(prefix,i)){ //和前面已经组合好的困难的串组合之后是否为困难的串 string s = prefix+i; //如果是就让前缀加上这个字母，把这个再当前缀 cout << s << endl; if(++cnt == n){ //达到指定数目，退出 cout << endl; exit(0); } dfs(l, n, s); //继续向下深搜 } } } int main(){ int l, n; cin >> n >> l; //n = 40, l = 3; dfs(l, n, ""); return 0; }
