7-5 困难的串

https://vjudge.net/problem/UVA-129
这题看了我很久，一是因为溯回法还不熟 理解上有误，二是将cnt看成了cur...

#define _CRT_SECURE_NO_WARNINGS    
#include<cstdio>  
#include<cstring>  
using namespace std;  
  
#define N 80+10  
int S[N];  
int n, L;  
int cnt;  
  
int dfs(int cur)  
{  
    if (cnt++ == n)  
    {  
        for (int i = 0; i < cur; i++)  
        {  
            printf("%c", 'A' + S[i]);  
            if ((i + 1) % 4 == 0)  
            {  
                if ((i + 1) % 64 == 0)printf("\n");  
                else if (i != cur - 1)printf(" ");  
            }  
        }  
        if (cur % 64)printf("\n");  
        printf("%d\n", cur);  
        return 0;//返回0表示已经找到了解  
    }  
    for (int i = 0; i < L; i++)  
    {  
        if(cnt!=1) if(i == S[cur - 1])continue; //除了第一个之外 其他的都不等于上一个 
        S[cur] = i;  
        //printf(" %d ",  cur );
        int ok = 1;  
        for (int j = 1; j * 2 <= cur + 1; j++)//枚举后缀的长度（注意不是整个串的长度）  
        {  
            int equal = 1;  
            for (int k = 0; k < j;k++)//检查前缀和后缀是否相等，S[cur-k]是后缀部分，S[cur-k-j]是前缀部分  
            if (S[cur - k] != S[cur - k - j]){ equal = 0; break; }  //如果能找到一个不等则递归 否则继续循环  这里break之后不会进入下一个if 而是继续循环 直至遍历完成
            if (equal){ ok = 0; break; }   //如果进入了 ， 就会再次进行选择字母
        }  
        if (ok)if (!dfs(cur + 1))return 0;//如果找到解，直接退出  
    }  
    return 1;  
}  
int main()  
{  
    //freopen("t.txt", "r", stdin);  
    while (~scanf("%d%d", &n, &L)&&(n||L))  
    {  
        cnt = 0;  
        memset(S, 0, sizeof(S));  
        dfs(0);  
    }  
    return 0;  
}

我做了一个小小的优化： if(cnt!=1) if(i == S[cur - 1])continue; //除了第一个之外 其他的都不等于上一个

7-5 困难的串

几个疑问：
0 后缀是什么？ 后缀在我理解起来就是所有的从新输入起的后一半 所有的后缀 是1，2，3，...，（cur+1）[数组实际使用元素个数]/2
1 为什么该溯回不用复原？ 因为cur的控制只会用到cur+1个元素 后面的元素会先被赋值
2 三个for分别控制什么？ 第一个：尝试字母的个数 第二个：与第三个结合 遍历所有后缀
3 奇数怎么办？
4 为什么有任意的不同即可？ 因为只要有一个不同 代表当前判断的这组后缀（1-（cur+1）/2中的某一组）不同
5 溯回在哪了？ 这里的溯回 跟前面一样 是因为前面一个选错而使得后面的值都不满足

 0  1  2  3  3  4  5  6  7  7  6  7  8  8  9  9  10  11  12  12  13  14  15  16  16  17  18  19  19  20  21  21  22  22  23  24  25  25  24  25  26  27

这是输入 30 3后，输出的cur，很明显，第一个回溯发生在 7 7 6 7 8 8 ， 实际上L>= 3时，回溯已经很少发生了，而且可以构造出无限长的串

另外 这里有个常用技巧 就是将字母换成数字来表