Skip to content

「POI2006」Palindromes

题解548 字
# 洛谷 # BZOJ # 2006 # POI # 字符串 # 哈希 # Trie
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

Johnny 喜欢玩文字游戏。

他写下了 nn 个回文串，随后将这些串两两组合，合并成一个新串。容易看出，一共会有 n2n^2 个新串。

两个串组合时顺序是任意的，即 a 和 b 可以组合成 ab 和 ba，另外自己和自己组合也是允许的。

现在他想知道这些新串中有多少个回文串，你能帮帮他吗？

#输入格式

第一行一个整数 nn。

接下来 nn 行，第 ii 行包含一个数 aia_i 和一个长度为 aia_i 的回文串。

#输出格式

输出一个整数，代表满足条件的新串的数量。

#输入输出样例

样例输入 #1

6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba

样例输出 #1

14

#数据范围与约定

保证输入中的所有字符串只包含小写字母，且所有串两两不同，所有回文串的长度和不超过 2×1062 \times 10^6。

#思路

有两个回文字符串 A,BA, B，由两个字符串拼接而成的新字符串 ABAB 是回文字符串的条件是 A,BA, B 中较短的串是较长的串的一个循环节。可以考虑枚举每个串的前缀，然后去查询这个前缀是否是另外一个较短的串，再判断组成的新串是否是回文的即可。

可以使用 std::unordered_map 或者 Trie + Hash 维护，下方的代码使用的是 std::unordered_map。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <string>
#include <unordered_map>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e6 + 5;

int n;
long long ans;
std::string s[N];
std::unordered_map<std::string, int> map;

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1, _; i <= n; i++) {
        cin >> _ >> s[i];

        map[s[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        std::string str, str1(s[i]);  // 卡常
        str.reserve(s[i].size());
        str1.reserve(s[i].size() << 1);

        for (char c : s[i]) {
            str.push_back(c);
            str1.push_back(c);

            if (map.count(str) && str1 == str + s[i]) {
                ans += static_cast<long long>(map[str]) * 2;
            }
        }
    }

    cout << ans - n << endl;

    return 0;
}