困难的串 Kryptn Factor Uva129

题目描述

输入格式

输出格式 

【输入样例】

7 3
30 3
0 0

【输出样例】

ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28

题意

将一个包含两个相邻的重复子串的子串，称为“容易的串”，其他为“困难的串”。 输入正整数n和l,输出由前l个字符组成的，字典序第k小的困难的串。

基本框架不难确定：从左往右依次考虑每个位置上的字符。因此，问题的关键在于如何判断当前字符串是否已经存在连续 的重复子串。

例如，判断ABACABA

• 检查所有长度为偶数的子串，分别判断每个子串的前一半是否等于后一半。
• 判断前串的后缀。

#include <stdio.h>
#include <string.h>
int S[50], L, n, cnt;
int dfs(int cur)
{
    if (n == cnt++)
    {
        for (int i = 0; i < cur; i++)
            printf("%c", 'A' + S[i]); // 将整型转换为字符输出
        printf("
");
        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;
}