问题描述
牛牛在书上看到一种字符串叫做回文串,当一个字符串从左到右和从右到左读都是一样的,就称这个字符串为回文串。牛牛又从好朋友羊羊那里了解到一种被称为优美的回文串的字符串,考虑一个长度为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;
}
