输出由前L个字母组成的第n个困难的串。困难的串是不包含相邻重复子串的串。
用困难的串生成一个串时，仅对其后缀进行判断，看是否是一个困难的串。不是就回溯继续生成。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #include<iostream>
#include<cstring>
using namespace std;
const int maxn=85;
int n,l,cnt,S[maxn];
int dfs(int cur){
if(cnt++==n){
for(int i=0;i<cur;i++){
if(i&&i%4==0&&i%64!=0) cout<<" ";
if(i&&i%64==0) cout<<endl;
cout<<(char)('A'+S[i]);
}
cout<<endl;
cout<<cur<<endl;
return 0;
}
for(int i=0;i<l;i++){
S[cur]=i;
bool ok=true;
for(int j=1;j*2<=cur+1;j++){
bool equal=true;
for(int k=0;k<j;k++)
if(S[cur-k]!=S[cur-k-j]){
equal=false;
break;
}
if(equal){
ok=false;
break;
}
}
if(ok) if(!dfs(cur+1)) return 0;
}
return 1;
}
int main(){
while(cin>>n>>l){
if(!n&&!l) break;
cnt=0;
memset(S,0,sizeof(S));
dfs(0);
}
return 0;
}
|
** 本文迁移自我的CSDN博客，格式可能有所偏差。 **