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

本文介绍了多少个回文可以通过字符从一个字符串的选择中形成的？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我代表朋友张贴这一点，因为我相信这是pretty的有趣的：

下面有他的实现（C ++，C也没关系虽然）。这是pretty的很长的话慢;他想知道什么是最快的算法可能这个（我很好奇太：D）。

 的#include＆LT;的iostream＆GT;
＃包括＆LT; CString的GT;

使用名字空间std;



无效find_palindrome（为const char *海峡，为const char *最大，长和放大器;计数）
{
    用于（为const char *开始=海峡;开始＆LT;最大;开始++）{
        算上++;
        为const char *结束=和strchr（开始+ 1，*开始）;
        而（完！= NULL）{
            算上++;
            find_palindrome（开始+ 1，最后，算）;
            结束=和strchr（结束+ 1，*开始）;
        }
    }
}


INT主（INT ARGC，字符* argv的[]）
{
    为const char * S =hihellolookhavealookatthis;
    长计数= 0;

    find_palindrome（S，strlen的（S）+ S，算）;

    COUT＆LT;＆LT;算上＆LT;＆LT; ENDL;
}

解决方案

首先，你的朋友的解决方案似乎都因为和strchr 中的错误可以搜索过去最高。即使你解决这个问题，解决的办法是指数级的时间。

对于一个更快的解决方案，您可以使用动态规划来解决这为O（n ^ 3）时间。这将需要为O（n ^ 2）额外的内存。请注意，对于长串，甚至64位整数，因为我在这里使用将不足以容纳解决方案。

 的#define MAX_SIZE 1000
长长的numFound [MAX_SIZE] [MAX_SIZE] //中间结果，由[指定startPosition] [endPosition]索引

长长countPalindromes（为const char * STR）{
    INT LEN =的strlen（海峡）;
    对于（INT startPos = 0; startPos＆LT; = LEN; startPos ++）
        对于（INT endPos = 0; endPos＆LT; = LEN; endPos ++）
            numFound [startPos] [endPos] = 0;

    对于（INT spanSize = 1; spanSize＆LT; = LEN; spanSize ++）{
        为（中间体startPos = 0; startPos＆其中; = LEN-spanSize; startPos ++）{
            INT endPos = startPos + spanSize;
            很长很长计数= numFound [startPos + 1] [endPos] //如果str [startPos]不是在回文，这将是计数
            焦炭CH =海峡[startPos]

            //如果str [startPos]在回文中，选择一个匹配的字符为回文结束
            对于（INT searchPos = startPos; searchPos＆LT; endPos; searchPos ++）{
                如果（STR [searchPos] == CH）
                    数+ = 1 + numFound [startPos + 1] [searchPos]
            }

            numFound [startPos] [endPos] =计数;
        }
    }
    返回numFound [0] [len个];
}

说明：

阵列 numFound [startPos] [endPos] 将与索引startPos到endPos包含在子回文数。

我们去了所有对指标（startPos，endPos），由短跨度开始和移动到更长的。对于每个这样的对，有两种选择：

在 STR字符[startPos] 不是回文。在这种情况下，有 numFound [startPos + 1] [endPos] 可能回文 - 一个数字，我们已经计算出
字符海峡[startPos] 是回文（在其开始）。我们通过串扫描以发现匹配的字符，以把在回文的末端。对于每一个这样的角色，我们使用已计算的结果 numFound 来找到的内部回文数的可能性。

修改

澄清：当我说字符串中包含的回文数，这包括非连续的子串。例如，所述回文阿巴包含在ABCA
这是可能采取的事实优势，以减少内存使用量为O（n）的计算 numFound [startPos] [X] 只需要知识 numFound [startPos + 1] [Y] 所有年。我是不会这样做的位置，因为它复杂化了codeA位。
pregenerating包含每个字母可以使内环更快的索引列表，但它仍然会为O（n ^ 3）整体。

I'm posting this on behalf of a friend since I believe this is pretty interesting:

Below there is his implementation (in C++, C is fine too though). It's pretty slow with very long words; he wants to know what's the fastest algorithm possible for this (and I'm curious too :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;
}

解决方案

First of all, your friend's solution seems to have a bug since strchr can search past max. Even if you fix this, the solution is exponential in time.

For a faster solution, you can use dynamic programming to solve this in O(n^3) time. This will require O(n^2) additional memory. Note that for long strings, even 64-bit ints as I have used here will not be enough to hold the solution.

#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];
}

Explanation:

The array numFound[startPos][endPos] will hold the number of palindromes contained in the substring with indexes startPos to endPos.

We go over all pairs of indexes (startPos, endPos), starting from short spans and moving to longer ones. For each such pair, there are two options:

The character at str[startPos] is not in the palindrome. In that case, there are numFound[startPos+1][endPos] possible palindromes - a number that we have calculated already.
character at str[startPos] is in the palindrome (at its beginning). We scan through the string to find a matching character to put at the end of the palindrome. For each such character, we use the already-calculated results in numFound to find number of possibilities for the inner palindrome.

EDIT:

Clarification: when I say "number of palindromes contained in a string", this includes non-contiguous substrings. For example, the palindrome "aba" is contained in "abca".
It's possible to reduce memory usage to O(n) by taking advantage of the fact that calculation of numFound[startPos][x] only requires knowledge of numFound[startPos+1][y] for all y. I won't do this here since it complicates the code a bit.
Pregenerating lists of indices containing each letter can make the inner loop faster, but it will still be O(n^3) overall.

这篇关于多少个回文可以通过字符从一个字符串的选择中形成的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！