题解 P3449 【[POI2006]PAL-Palindromes】

KSkun

2018-02-07 00:59:46

Solution

感谢远航之曲提供思路,这是他的原博文[bzoj 1524 [POI2006]Pal | 远航休息栈](http://www.yhzq-blog.cc/bzoj-1524-poi2006pal/)。 另外本题解同步发布于我的博客[[POI2006]PAL-Palindromes 题解 | KSkun's Blog](https://ksmeow.moe/pal_poi06_sol/),欢迎来逛~ # 题解 这个拼接成回文串的情况,肯定是较短串是较长串的前缀时成立,因此可以Trie树处理这些字符串,然后枚举每个字符串的前缀是否也在里面,在的话试着拼接一下。 判断是否是回文串的方法可以用哈希处理。前串的哈希乘上哈希基的后串长次方再加后串的哈希就能完成拼接。对于每一对这样的字符串显然是反着拼也成立,统计答案是要乘2。自己和自己拼算了两次要减掉。 # 代码 ```cpp // 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; } ```