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

Question

我代表一位朋友发帖,因为我觉得这很有趣:

取字符串"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;
}

Answer 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),从短跨度开始到移动到较长跨度.对于每个这样的对,有两种选择:

1. 该角色str[startPos]不在回文区.在这种情况下,有numFound[startPos+1][endPos]可能的回文 - 我们已经计算过的数字.

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

编辑:

• 澄清:当我说"字符串中包含的回文数"时,这包括非连续的子串.例如,回文"aba"包含在"abca"中.

• 通过利用计算numFound[startPos][x]仅需要知道numFound[startPos+1][y]所有y 的事实,可以将存储器使用减少到O(n).我不会在这里这样做,因为它使代码复杂化了一些.

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

Answer 2

我有办法在O(N ^ 2)时间和O(1)空间中做到这一点,但我认为必须有其他更好的方法.

基本的想法是长回文必须包含小回文,所以我们只搜索最小匹配,这意味着两种情况:"aa","aba".如果我们找到了,那么扩展以查看它是否是长回文的一部分.

    int count_palindromic_slices(const string &S) {
        int count = 0;

        for (int position=0; position<S.length(); position++) {
            int offset = 0;

            // Check the "aa" situation
            while((position-offset>=0) && (position+offset+1)<S.length() && (S.at(position-offset))==(S.at(position+offset+1))) {
                count ++;
                offset ++;
            }

            offset = 1;  // reset it for the odd length checking
            // Check the string for "aba" situation
            while((position-offset>=0) && position+offset<S.length() && (S.at(position-offset))==(S.at(position+offset))) {
                count ++;
                offset ++;
            }
        }
        return count;
    }

2012年6月14日经过一番调查,我相信这是最好的方法.比接受的答案快.