困难的串（dfs）

困难的串

题意：

如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。例如， BB、ABCDABCD都是容易的串，而D、DC、ABDAD、CBABCBA都是困难的串。

输入正整数n和L，输出由前L个字符组成的、字典序第k个困难的串。例如，当L=3时，前7个困难的串 分别为A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。输入保证答案不超过80个字符。

样例输入：

7 3

30 3

样例输出：

ABACABA

ABACABCACBABCABACABCACBACABA

思路：构建一个字符串a[]，往其中不断增加满足条件的字符，直至字符串大小为n，即为所求字符串；

假设当前串长度为cur，则字符串a[cur-1]的所有子串都是困难的，所以只需判断字符串a[cur]是否困难即可；

代码：

1 #include <bits/stdc++.h>
 2 #define MAXN 100
 3 using namespace std;
 4 
 5 int a[MAXN], n, l, cnt=0;
 6 
 7 int dfs(int cur)
 8 {
 9     if(cnt++==n)    //**每当cnt+1必能增加一个合法字符，当cnt=n时即得到所求字符串
10     {
11         for(int i=0; i<n; i++)
12         {
13             printf("%c", a[i]+'A');
14         }
15         printf("\n");
16         return 0;
17     }
18     for(int i=0; i<l; i++)
19     {
20         a[cur]=i;              //****尝试选中字符i+"A"
21         int flag=1;
22         for(int j=1; j*2<=cur+1; j++)   //***当前构建长度为2*j的字符串
23         {
24             int k;
25             for(k=0; k<j; k++)      //***判断当前字符串是否是容易的串
26             {
27                 if(a[cur-k]!=a[cur-k-j])
28                 {
29                     break;        
30                 }
31             }
32             if(k==j)  //***如果k=j，即其为容易的串
33             {
34                 flag=0;
35                 break;
36             }
37         }
38         if(flag)  //***如果当前串为困难的串，并且cnt!=n，继续递归，如果cnt=n，递归结束，直接退出
39         {
40             if(!dfs(cur+1))
41             {
42                 return 0;
43             }
44         }
45     }
46     return 1;
47 }
48 
49 int main(void)
50 {
51     std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
52     cin >> n >> l;
53     dfs(0);
54     return 0;
55 }

原文链接: https://www.cnblogs.com/geloutingyu/p/5852348.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍