字符串的分散回文的返回计数

Question

我们必须在给定的字符串中找到散文回文字符串，并在字符串中返回散文回文数。例如，给定字符串“ aabb”，分散回文式为a，aa，aab，aabb，a，abb，b，bb和b。这里有9个散点回文的子字符串。

我曾考虑过蛮力方法，即生成所有子字符串并检查它们，但我想找到一种更好的方法。

Answer 1

首先，让我们考虑如何确定字符串是否可以是散点回文。

让我们考虑我们的字符串仅由小写字符组成的情况。

一个字符串可以被认为是分散的回文，如果：

1. 当字符串长度为偶数时：字符串中出现的所有字符必须出现偶数次。
2. 字符串长度为奇数时：字符串中只有一个字符出现奇数次，其他字符出现偶数次。

所以要检查一个字符串是否可以是散点回文，我们只需要检查字符串中每个字符出现的次数。这可以在 O(n) 中完成，其中 n 是字符串的长度。

对于您的解决方案：生成所有子串的时间复杂度为 O(n ² )。为了检查子串是否是散布回文，我们需要另一个 O(n)。因此，总时间复杂度为 O(n ³ )。

我们可以在检查的同时减少 O(n) 因子，这可以将总时间复杂度降低到 O(n ² )。

为此，您可以采用大小为 n*26 的二维数组，其中 n 是字符串的长度。将该数组设为 A[n][26]。所以 A[i][j] 存储了^第j^个字符*从 0 到 i的总出现次数。

所以对于字符串“abca”，你的数组看起来像

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

现在对于从索引 l 到 r 的任何子字符串， A[r]-A[l-1] 为您提供子字符串中每个字符的出现。要检查这是否可以是散点回文，我们需要 26 次操作。因此，解决方案的时间复杂度变为 O(n ² * 26)，它与 ​​O(n ² )渐近相同。

这里我们使用了 n*26 的额外空间。这可以通过更好的方法避免。

我们不是将每个字符的出现存储在数组中，而是将其存储为整数。如果^第i^个位从 lsb 为 '1' 表示^第j^个索引，则表示^第i^个字符从 0 到^第j^个索引出现奇数次。如果它是'0'，则表示^第i^个字符*出现了偶数次。

考虑这个例子，其中输入字符串是“abca”

所以我们的辅助数组将是

1 3 7 6

1 -> (0001) ['a' 出现过一次]

3 -> (0011) ['a' 和 'b' 出现过一次]

7 -> (0111) ['a'、'b' 和 'c' 各出现一次]

6 -> (0110) ['a' 出现了两次，而 'b' 和 'c' 出现了一次]

因此，现在对于从索引 l 到 r A[r] xor A[l-1] 的任何子字符串，如果它是 0 或 2 的幂，则该整数将包含在最终答案中。（它全为 0 位或只有一个“1”位）

伪代码如下：

input string = s
ans = 0
n = s.length

for i=1:n
    A[i]=A[i-1]^(1<<(s[i-1]-97))

for i=1:n
    for j=i;n
        x=A[j]^A[i-1]
        if (x&(x-1)) == 0    //if x is a power of 2 or not 
            ans++;
        endif
    endfor
endfor

散布回文的总数存储在ans 中。

该方法的空间复杂度为 O(n)。此外，它的运行时间将比之前解释的方法更好。

• 这里^第i^个字符是指考虑到 'a' 是^第0^个字符，'b' 是第一个字符等等的字符。

Answer 2

NEERC 2012-2013中也有类似任务（问题H. Hyperdrome，在此声明）。幻灯片解释解决方法在这里。如有必要，我可以详细解释（我在比赛中解决了）。

小写字母字符串的解决方案：

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main()
{
    long long answer = 0;
    string s;
    cin >> s;
    map<int, int> m;
    m[0] = 1;
    int x = 0;
    for (auto& c : s) {
        int d = c - '0';
        x ^= 1 << d;
        answer += m[x];
        for (int i = 0; i < 26; ++i) {
            answer += m[x ^ (1 << i)];
        }
        m[x] += 1;
    }
    cout << answer << endl;
    return 0;
}

复杂度是字母大小（）O(|A| * n * log(n))在哪里，字符串的长度在哪里。是访问的困难（可用具有复杂性的哈希代替）。|A||A| = 26nslog(n)mapO(1)

Answer 3

任何单个字符都是分散回文。任何一对相同的字符都是分散回文。如果 P 是分散回文，则 C + P + C 也是分散回文，其中 C 是字符，+ 是字符串连接运算符。这导致了以下算法，我们通过从给定字符串中选取字符来递归地构建所有可能的回文。下面是伪代码。注意|S|是 中的字符数S。

让S为给定字符串中的字符集。调用后countScatterPalindrome() count会得到 中分散回文的个数S。

count = 0;  // The number of scatter palindome in S.

countScatterPalindrome(S)
{
    if |S| == 1 then
        count++;
        return true;

    if |S| == 0
        return true; 

    remove 2 characters that are equal from S

    if countScatterPalindrome(S) == true
        count++
        return true;

    return false;
}