题目描述
将一个包含两个相邻的重复子串的子串，称为“容易的串”，其他为“困难的串”。 输入正整数n和l,输出由前l个字符组成的，字典序第k小的困难的串。
输入样例
7 3 30 3 0 0
输出样例
7 3 ABAC ABA 7 30 3 ABAC ABCA CBAB CABA CABC ACBA CABA 28 0 0
思路解析: 这个题是求字符串的困难串,在进行判断时,由于困难串比较难判断,我们来判断简单串,如果判断简单串呢?我们只需要判断字符串的后缀子串即可.因为一个困难串+一个字符,相邻子串只可能出现在后面.所以我们只需要判断后缀即可.
之后采用DFS解决即可.
参考代码
#include<iostream> using namespace std; int n,cnt,L,S[100]; int dfs(int cur){ //判断困难串是否达到了n if(cnt++==n){ for(int i = 0; i < cur; i++){ if(i&&i%4==0&&i!=64){ cout<<" "; }else if(i==64){ cout<<endl; } cout<<char('A'+S[i]); } cout<<endl; cout<<cur<<endl; return 0;//结束 } for(int i = 0;i < L;i++)//依次判断cur位置可能出现的字符. { 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]){//不相等,说明以J*2为后缀不是简单串 (但该字符串未必就是困难串,因为还有其他后缀,只有所有后缀都遍历过且都不是简单串 才成立. ) equal = 0; break; } } if(equal){//equal:0 困难串 equal:1简单串 如果是简单串则结束该字符串,进行开始尝试下一个字符串. ok = 0; break; } } if(ok){ if(!dfs(cur+1)){//如果是困难串,则进行继续深搜.当返回后判断是否已经找够,如果找够了,则结束该层dfs. 没找够则继续往后寻找 return 0; } } } return 1; } int main() { while(scanf("%d %d",&n,&L)!=EOF &&n &&L){ cnt = 0; dfs(0); } return 0; }
