首页 > 代码库 > 困难的串

困难的串

2024-07-02 15:44:27   224人阅读

如果一个字符串包含两个相邻的重复字串，则称它是“容易的串”，其他串称为“困难的串”。例如，BB,ABCDACABCAB,ABCDABCD都是容易的，
而D,DC,ABDAB,CBABCBA都是困难的。输入正整数n和L，输出由前L个字符组成的，字典序第k小的困难的串。
例如，当L=3时，前7个困难的串分别为：A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA.输入保证答案不超过80个字符。
样例输入：
7 3
30 3
样例输出：
ABACABA
ABACABCACBABCABACABCACBACABA

 1 #include<iostream>
 2 using namespace std;
 3 int a[100];
 4 int count=0;            
 5 int n,L;                                                                        //如果在main函数中生命，则dfs参数需要修改，否则无法识别n和L
 6 //void dfs(int a[], int cur, int L, int n)
 7 void dfs(int cur)
 8 {
 9     if(cur==n)
10     {
11         for(int i=0; i<cur; i++)
12             cout<<char(‘A‘+a[i])<<" ";
13         cout<<endl;
14         count++;
15         return ;                                                                //如注释该句，则运行会报错。
16     }
17     for(int i=0; i<L; i++)
18     {
19         a[cur]=i;
20         int ok=1;
21         for(int j=1; j*2<=cur+1; j++)
22         {
23             int equal=1;
24             for(int k=0; k<j; k++)
25                 if(a[cur-k]!=a[cur-k-j])
26                 {
27                     equal=0;
28                     break;
29                 }
30             if(equal)
31             {
32                 ok=0;
33                 break;
34             }
35         }
36         if(ok)    dfs(cur+1);
37         //    dfs(a,cur+1, L, n);
38     }
39 }
40 void main()
41 {
42     memset(a,-1,100);
43     //    int n,L;
44     cin>>n>>L;
45     dfs(0);
46     //dfs(a, 0, L, n);
47     cout<<count<<endl;
48 }

 


联系
我们