算法竞赛：困难的串

[yooocen]

如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。例如，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

L=1 就是A，L=2就是AB，L=3就是ABC

【解析】：

1. 首先怎么判断是否有连续子串，比方说ABACA已经被判断没有连续子串了，那只需要考虑再加一个字符是否是有连续子串，比方说我加一个A，那么ABCACAA最后的A和A相等就直接不行，我加一个B，那么首先A和B不相等，可以，那么AC和AB是否相等呢？B和C不想等直接可以，不需要再判断A和A相不相等，字符串直接只要一个字符不相等就是不相等。
2. 关于for(int j=1;j*2<=cur+1;j++)和for(int k=0;k<j;k++)应该这么说k最大的值就是j-1，那么 *cur - k - j = cur - j + 1 + j = cur - 2 j + 1 = cur - cur -1 +1 = 0
3. 我们来看一下30 3的时候的解答树：

   A
   AB
   ABA
   ABAC
   ABACA
   ABACAB
   ABACABA
   ABACABC
   ABACABCA
   ABACABCAC
   ABACABCACB
   ABACABCACBA
   ABACABCACBAB
   ABACABCACBABC
   ABACABCACBABCA
   ABACABCACBABCAB
   ABACABCACBABCABA
   ABACABCACBABCABAC
   ABACABCACBABCABACA
   ABACABCACBABCABACAB
   ABACABCACBABCABACABC
   ABACABCACBABCABACABCA
   ABACABCACBABCABACABCAC
   ABACABCACBABCABACABCACB
   ABACABCACBABCABACABCACBA
   ABACABCACBABCABACABCACBAB
   ABACABCACBABCABACABCACBAC
   ABACABCACBABCABACABCACBACA
   ABACABCACBABCABACABCACBACAB
   ABACABCACBABCABACABCACBACABA

   可以看出第7和28个字典序是有多个选择的，这也是深度搜索的一个特点，也就是说明了为什么递归了30次，实际的层次只有28层

【代码】：

#include<stdio.h>
#include<string.h>
int S[50],L,n,cnt;
int dfs(int cur)
{
    for(int i=0;i<cur;i++)
        printf("%c",'A'+S[i]);  // 将整型转换为字符输出
    printf("\n");
    if(n==cnt++)
    {
//        for(int i=0;i<cur;i++)
//            printf("%c",'A'+S[i]);  // 将整型转换为字符输出
        printf("\n");
        printf("%d",cur);
        return 0;
    }
    for(int i=0;i<L;i++)
    {
        S[cur]=i;
        int ok=1;
        for(int j=1;j*2<=cur+1;j++)  // 将cur分半
        {
            int equal=1;    // 标记
            for(int k=0;k<j;k++)
                if(S[cur-k]!=S[cur-k-j]) // 检查后一半是否等于前一半
                {
                    equal=0;
                    break;
                }
            if(equal)   //如果等于，跳出
            {
                ok=0;
                break;
            }
        }
        if(ok) if(!dfs(cur+1)) return 0; // 如果找到解，则直接退出，找到解时，return 0，且ok=1
    }
    return 1;
}
int main()
{
    while(~scanf("%d %d",&n,&L))
    {
        // 置0，以免影响下组数据
        cnt=0;
        memset(S,0,sizeof(S));
        dfs(0);
    }
    return 0;
}