题目地址：洛谷：【P3449】[POI2006]PAL-Palindromes – 洛谷

题目描述

Little Johnny enjoys playing with words. He has chosen nnn palindromes (a palindrome is a wordthat reads the same when the letters composing it are taken in the reverse order, such as dad, eye orracecar for instance) then generated all n2n^2n2 possible pairs of them and concatenated the pairs intosingle words. Lastly, he counted how many of the so generated words are palindromes themselves.
However, Johnny cannot be certain of not having comitted a mistake, so he has asked you to repeatthe very same actions and to give him the outcome. Write a programme which shall perform thistask for you.
TaskWrite a programme which:
reads the palindromes given by Johnny from the standard input, determines the number of words formed out of pairs of palindromes from the input, which are palindromes themselves, writes the outcome to the standard output.
给出n个回文串s1, s2, …, sn 求如下二元组(i, j)的个数 si + sj 仍然是回文串 规模 输入串总长不超过2M bytes

输入输出格式

输入格式：
The first line of the standard input contains a single integer n , n≥2 , denoting the number ofpalindromes given by Johnny. The following n lines contain a description of the palindromes. The (i+1)’st line contains a single positive integer ai denoting the length of i’th palindrome and apalindrome of ai small letters of English alphabet. The number ai is separated from the palindromeby a single space. The palindromes in distinct lines are distinct. The total length of all palindromesdoes not exceed 2 000 000.
输出格式：
The first and only line of the standard output should contain a single integer: the number of distinctordered pairs of palindromes which form a palindrome upon being concatenated.

输入输出样例

输入样例#1：

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

输出样例#1：

14

题解

感谢远航之曲提供思路，这是他的原博文bzoj 1524 [POI2006]Pal | 远航休息栈。
这个拼接成回文串的情况，肯定是较短串是较长串的前缀时成立，因此可以Trie树处理这些字符串，然后枚举每个字符串的前缀是否也在里面，在的话试着拼接一下。判断是否是回文串的方法可以用哈希处理。前串的哈希乘上哈希基的后串长次方再加后串的哈希就能完成拼接。对于每一对这样的字符串显然是反着拼也成立，统计答案是要乘2。自己和自己拼算了两次要减掉。

代码

// Code by KSkun, 2018/2
#include <cstdio>
#include <cstring>
#include <string>

const int MO = 1e9 + 7, base = 255;

int ch[2000005][26], tot = 1;
int wrd[2000005], cnt[2000005];

int n, len[2000005], hash[2000005], bpow[2000005];
std::string str[2000005];
char strt[2000005];
long long ans = 0;

inline void insert(char* str, int id) {
    int t = 1;
    for(int i = 0; i < len[id]; i++) {
        if(!ch[t][str[i] - 'a']) {
            t = ch[t][str[i] - 'a'] = ++tot;
        } else {
            t = ch[t][str[i] - 'a'];
        }
    }
    wrd[t] = id;
    cnt[t]++;
}

inline int calhash(char* str, int len) {
    long long res = 0;
    for(int i = 0; i < len; i++) {
        res = (res * base + str[i]) % MO;
    }
    return res;
}

int main() {
    scanf("%d", &n);
    bpow[0] = 1;
    for(int i = 1; i < 2000005; i++) {
        bpow[i] = (1ll * bpow[i - 1] * base) % MO;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d%s", &len[i], strt);
        insert(strt, i);
        hash[i] = calhash(strt, len[i]);
        str[i] = strt;
    }
    for(int i = 1; i <= n; i++) {
        int u = 1;
        for(int j = 0; j < len[i]; j++) {
            u = ch[u][str[i][j] - 'a'];
            if(wrd[u]) {
                if((1ll * hash[wrd[u]] * bpow[len[i]] % MO + hash[i]) % MO == 
                    (1ll * hash[i] * bpow[len[wrd[u]]] % MO + hash[wrd[u]]) % MO) {
                    ans = ans + 1ll * cnt[u] * 2;
                }
            }
        }
    }
    printf("%lld", ans - n);
    return 0;
}