通过从字符串中选择字符可以形成多少回文？

一尘不染

通过从字符串中选择字符可以形成多少回文？

algorithm

我代表朋友发布此消息，因为我认为这很有趣：

取字符串“ abb”。通过省略少于字符串长度的任意数量的字母，我们得到7个字符串。

abb ab ab bb abb

在这4个回文中。

对于字符串类似

“
hihellolookhavealookatthispalindromexxqwertyuiopasdfghjklzxcvbnmmnbvcxzlkjhgfdsapoiuytrewqxxsoundsfamiliardoesit”

（长度为112的字符串）可以形成2 ^ 112-1的字符串。

在这些回文中有多少？

下面是他的实现（尽管在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;
}

阅读 195

2020-07-28

共1个答案

一尘不染

首先，您朋友的解决方案似乎存在错误，因为strchr可以搜索过去max。即使您解决此问题，解决方案也将是指数级的。

对于更快的解决方案，您可以使用动态编程在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），从短跨度开始，然后过渡到更长的对。对于每个这样的对，都有两个选项：

处的字符str[startPos]不在回文中。在这种情况下，numFound[startPos+1][endPos]可能存在回文-我们已经计算出一个数。
字符位于str[startPos]回文（开始时）。我们扫描字符串以找到匹配的字符并放在回文末尾。对于每个这样的角色，我们使用已经计算出的结果numFound来寻找内部回文的可能性。

编辑：

澄清：当我说“字符串中包含的回文数”时，其中包括不连续的子字符串。例如，回文“ aba”包含在“ abca”中。
通过利用numFound[startPos][x]仅计算numFound[startPos+1][y]y就需要y 的事实，可以将内存使用量减少到O（n）。我不会在这里做这件事，因为它会使代码复杂一些。
包含每个字母的索引的预生成列表可以使内部循环更快，但总体上仍为O（n ^ 3）。

2020-07-28