题解 P3449 【[POI2006]PAL-Palindromes】

2018-02-07 00:59:46


感谢远航之曲提供思路,这是他的原博文bzoj 1524 [POI2006]Pal | 远航休息栈

另外本题解同步发布于我的博客[POI2006]PAL-Palindromes 题解 | KSkun's Blog,欢迎来逛~

题解

这个拼接成回文串的情况,肯定是较短串是较长串的前缀时成立,因此可以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;
}