计算字符串组合成回文的数量（POJ 3376）

本题是ACM编程挑战题目POJ 3376，题目名为“Finding Palindromes”，主要涉及字符串处理和哈希（Palindrome Detection）。题目背景是，给定一个包含n个字符串的输入，每个字符串由小写字母组成，且总长度不超过2,000,000。任务是通过将这些字符串两两组合，形成n乘以n对新单词，并计算其中有多少个新单词是回文（即正读反读都一样的单词）。 **输入描述**： - 第一行包含一个整数n，表示字符串的数量。 - 接下来的n行，每行描述一个字符串，包含两个部分：字符串长度li（以空格隔开），然后是一个长度为li的由小写英文字母组成的字符串。 **输出描述**： - 输出一个整数，表示生成的回文单词总数。 **示例**： - 输入： ``` 3 1a 2ab 2ba ``` - 输出： ``` 5 ``` - 解释：5个回文单词包括 "aa", "aba", "b", "ab", 和 "aba"。 **解题思路**： 1. 首先，对输入的字符串进行预处理。由于字符串长度不大，可以遍历每个字符串，计算出其长度并存储在数组`l[]`中。同时，可以创建一个辅助数组`sz[]`记录每个字符串出现的次数，以便后续计算回文组合时考虑重复。 2. 对于每个字符串，将其转换成一个字符数组`chars[]`。为了快速查找回文子串，可以使用Manacher's Algorithm或者KMP算法（Kleene's Minimal Patter Matching Algorithm）来计算字符串中的最长回文子串。这里我们选择Manacher's Algorithm，因为它对于偶数长度的字符串有更快的处理速度。算法的核心思想是利用已知回文半径（中心对称的回文长度）来避免重复计算。 3. 创建一个名为`next[]`的数组用于存储每个位置的回文半径，以及一个临时数组`t[]`存储当前字符串的回文中心。遍历整个字符串，根据Manacher's Algorithm的规则更新`next[]`数组。 4. 当所有字符串处理完毕后，可以通过统计`sz[]`数组中的奇数长度字符串和`next[]`数组中非零值来计算回文组合。对于每个长度为奇数的字符串，它本身就是一个回文，所以直接累加到结果`ans`中。对于长度为偶数的字符串，可以计算与自身配对形成的回文，即取`sz[i] * (sz[i] - 1) / 2`对回文。同时，还可以计算与另一个字符串配对形成的回文，即每个偶数长度字符串与其相邻的奇数长度字符串配对，共`sz[i] * sz[j]`对，其中`j = i - next[i]`或`j = i + next[i]`。 5. 最后，输出计算得到的回文单词总数`ans`。 **参考代码**： ```cpp #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; // ... (继续实现Manacher's Algorithm、更新next[]和计算回文数量的部分) int main() { // ... (读取输入、处理字符串、更新数据结构) for (int i = 0; i < n; ++i) { ans += sz[i]; // 奇数长度字符串本身就是回文 if (next[i] > 0) { ans += sz[i] * (sz[i] - 1) / 2; // 偶数长度字符串与自身配对 if (i - next[i] >= 0 && i + next[i] < n) ans += sz[i] * sz[i - next[i]]; // 偶数长度字符串与相邻奇数长度配对 } } printf("%lld\n", ans); return 0; } ``` 解决POJ 3376 Finding Palindromes的关键在于使用Manacher's Algorithm高效地检测字符串中的回文，结合字符串出现次数数组来统计最终的回文单词总数。