c++ - 从一个字符串中选择字符可以形成多少个回文？

Question

我代表 friend 发布此内容，因为我认为这很有趣:

Take the string "abb". By leaving out any number of letters less than the length of the string we end up with 7 strings.

a b b ab ab bb abb

Out of these 4 are palindromes.

Similarly for the string

"hihellolookhavealookatthispalindromexxqwertyuiopasdfghjklzxcvbnmmnbvcxzlkjhgfdsapoiuytrewqxxsoundsfamiliardoesit"

(a length 112 string) 2^112 - 1 strings can be formed.

Out of these how many are palindromes??

下面是他的实现(在 C++ 中，C 也很好)。很长的话很慢；他想知道最快的算法是什么(我也很好奇:D)。

#include <iostream>
#include <cstring>

using namespace std;



void find_palindrome(const char* str, const char* max, long& count)
{
    for(const char* begin = str; begin < max; begin++) {
        count++;
        const char* end = strchr(begin + 1, *begin);
        while(end != NULL) {
            count++;
            find_palindrome(begin + 1, end, count);
            end = strchr(end + 1, *begin);
        }
    }
}


int main(int argc, char *argv[])
{
    const char* s = "hihellolookhavealookatthis";
    long count = 0;

    find_palindrome(s, strlen(s) + s, count);

    cout << count << endl;
}

Answer 1

首先，您 friend 的解决方案似乎有一个错误，因为 strchr 可以搜索超过 max。即使你解决了这个问题，解决方案也是指数级的。

要获得更快的解决方案，您可以使用 dynamic programming在 O(n^3) 时间内解决这个问题。这将需要 O(n^2) 额外的内存。请注意，对于长字符串，即使是我在这里使用的 64 位整数也不足以容纳解决方案。

#define MAX_SIZE 1000
long long numFound[MAX_SIZE][MAX_SIZE]; //intermediate results, indexed by [startPosition][endPosition]

long long countPalindromes(const char *str) {
    int len = strlen(str);
    for (int startPos=0; startPos<=len; startPos++)
        for (int endPos=0; endPos<=len; endPos++)
            numFound[startPos][endPos] = 0;

    for (int spanSize=1; spanSize<=len; spanSize++) {
        for (int startPos=0; startPos<=len-spanSize; startPos++) {
            int endPos = startPos + spanSize;
            long long count = numFound[startPos+1][endPos];   //if str[startPos] is not in the palindrome, this will be the count
            char ch = str[startPos];

            //if str[startPos] is in the palindrome, choose a matching character for the palindrome end
            for (int searchPos=startPos; searchPos<endPos; searchPos++) {
                if (str[searchPos] == ch)
                    count += 1 + numFound[startPos+1][searchPos];
            }

            numFound[startPos][endPos] = count;
        }
    }
    return numFound[0][len];
}

解释:

数组 numFound[startPos][endPos] 将保存索引 startPos 到 endPos 的子字符串中包含的回文数。

我们遍历所有索引对(startPos、endPos)，从短跨度开始，到更长的跨度。对于每一对这样的对，有两个选项:

1. str[startPos] 处的字符不在回文中。在这种情况下，有 numFound[startPos+1][endPos] 个可能的回文 - 我们已经计算过一个数字。

2. str[startPos] 处的字符在回文中(在其开头)。我们扫描字符串以找到匹配的字符放在回文的末尾。对于每个这样的字符，我们使用 numFound 中已经计算的结果来查找内部回文的可能性数。

编辑:

• 澄清:当我说“字符串中包含的回文数”时，这包括不连续的子字符串。例如，回文“aba”包含在“abca”中。

• 利用 numFound[startPos][x] 的计算只需要知道 numFound[startPos +1][y] 为所有 y。我不会在这里这样做，因为它会使代码有点复杂。

• 预先生成包含每个字母的索引列表可以使内部循环更快，但总体上仍然是 O(n^3)。