优美的回文串

问题描述

牛牛在书上看到一种字符串叫做回文串,当一个字符串从左到右和从右到左读都是一样的,就称这个字符串为回文串。牛牛又从好朋友羊羊那里了解到一种被称为优美的回文串的字符串,考虑一个长度为N只包含大写字母的字符串,写出它所有长度为M的连续子串(包含所有可能的起始位置的子串,相同的子串也要计入),如果这个字符串至少有K个子串都是回文串,我们就叫这个字符串为优美的回文串。现在给出一个N,牛牛希望你能帮他计算出长度为N的字符串有多少个是优美的回文串(每个位置都可以是'A'~'Z'的一个。)

输入描述

输入数据包括三个整数N, M, K(2 ≤ N ≤ 11, 2 ≤ M ≤ N, 0 ≤ K ≤ 11).

输出描述

输出一个整数,表示所求的字符串个数.

输入例子

2 2 1

输出例子

26
长度为2的字符串,它长度为2的子串只有它自身。长度为2的回文串有"AA","BB","CC"..."ZZ",一共26种。

分析

假设有一个长度为N的字符串S，S有一个长度为M的连续子串T。T包含了U种不同的字符。T的每种不同的字符都可以被替换掉，由于字符集为{A, B, C,...,Z}，所以总共有26*25*23*...*(27-U)种替换方法。我们现在要做的，就是在长度为N的字符串集合中，枚举所有长度为M、包含U种不同字符的字符串。

note

使用替换法，可以大大减少枚举空间，提高效率。计算复杂度为O(n!)。n最大为11，所以算法还是有可行性的。

代码

#include <iostream>
#include <algorithm>

using namespace std;

int m, k, n;
char str[12];
long long fact[12], res = 0;

bool isElegantPalindrome()
{
    int cnt = 0;
    for (int i = 0; i < n - m + 1; i++)
    {
        bool flag = true;
        for (int j = 0; j < m / 2; j++)
        {
            if (str[i + j] != str[i + m - 1 - j])
            {
                flag = false;
                break;
            }
        }
        if (flag)
            cnt++;
    }

    return cnt >= k;
}

void dfs(int len, int typeNum)
{
    if (len == 0) 
    {
        if (isElegantPalindrome())
            res += fact[typeNum];
        return;
    }

    for (int i = 0; i <= typeNum; i++) 
    {
        str[len - 1] = 'a' + i;
        dfs(len - 1, max(typeNum, i + 1));
    }
}

int main() 
{
    cin >> n >> m >> k;

    fact[0] = 0; fact[1] = 26;
    for (int i = 2; i <= n; i++) 
        fact[i] = fact[i - 1] * (27 - i);

    dfs(n, 0);
    cout << res << endl;

    return 0;
}