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; //除了第一个之外其他的都不等于上一个

图片发自简书App

几个疑问：
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时，回溯已经很少发生了，而且可以构造出无限长的串

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

最后编辑于：2017.12.14 08:51:57