字符串的分散回文的返回计数 [英] return count of scatter palindrome of a string

问题描述

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

We have to find scatter palindrome strings inside given string and return number of scatter palindrome in string. For example given string "aabb", the scatter palindromes are a, aa, aab, aabb, a, abb, b, bb, and b. Here there are 9 sub-strings that are scatter palindrome.

我想到了蛮力方法，即生成所有子字符串并检查它们，但是我想找到更好的方法。

I have thought of brute force approach, i.e generating all sub-string and checking them, but I'd like to find a better approach.

推荐答案

NEERC 2012-2013遇到了类似的任务（问题H. Hyperdrome，声明此处）。解释该解决方案的幻灯片为此处。如有必要，我可以详细解释（我在比赛中解决了）。

A similar task was at NEERC 2012-2013 (problem H. Hyperdrome, statement here). Slide explaining the solution is here. I can explain in more detail if necessary (I solved it during the contest).

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

Solution for string of lowercase letters:

#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 | = 26 ）和 n 是字符串 s 的长度。 log（n）是访问 map 的难点（可以用复杂度<$ c $的哈希代替） c> O（1））。

Complexity is O(|A| * n * log(n)) where |A| is alphabet size (|A| = 26) and n is length of string s. log(n) is the difficulty of accessing to map (can be replaced with a hash with complexity O(1)).

这篇关于字符串的分散回文的返回计数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！