Finding Palindromes 这是一道字符串的综合题。 题意：给你n个字符串，求能够拼接成多少个回文串。(拼接定义:a + b or b + a)。 题解：对于字符串a，如果有字符串x的倒序与a的前缀匹配,同时字符串a的后缀是一个回文串，那么它们必然能够组成回文串。同时还有如果a是字符串x的倒序后缀，如果字符串的前缀是回文串，那么也必然能拼接成回文串。 举个例子: ab ba a abaa 对于字符串 a 来说 , 它与字符串 ba 的倒序 ab 的前缀匹配了，而它的后缀b也是一个回文串，那么它们必然能够拼接成回文串， 还有的另一种情况就是，对于a来说它与abaa的倒序 aaba的前缀匹配了，而它之后aba ，又是一个回文串，所以这种情况也是能够拼接的。
#include <iostream> #include <string.h> #include <algorithm> #include <stdio.h> #include <math.h> #define ll long long using namespace std; const int maxn = 2e6+10; char s[maxn] , tmp[maxn*2]; bool pre[maxn],suf[maxn]; int p[maxn*2],tot = 0; int start[maxn],vis[maxn],qian[maxn]; int tr[maxn][28]; void init() { for(int i=0;i<=tot;i++) { vis[i] = qian[i] = 0; for(int j=0;j<26;j++) tr[i][j] = 0; } tot = 0; } void trie(int x) { int p = 0; for(int i=start[x+1]-1;i>=start[x];i--) { int t = s[i] - 'a'; qian[p] += pre[i]; if(!tr[p][t]) tr[p][t] = ++tot; p = tr[p][t]; } vis[p] += 1; } void manacher(int x) { int len = 1; tmp[0] = '$'; for(int i=start[x];i<start[x+1];i++) { tmp[len++] = '#'; tmp[len++] = s[i]; pre[i] = 0; suf[i] = 0; } tmp[len] = '#'; tmp[len+1] = 0; int mx = 0 , id = 0; for(int i=2;i<len;i++) { if(mx<=i) p[i] = 1; else p[i] = min(mx-i,p[id*2-i]); while(tmp[i+p[i]]==tmp[i-p[i]]) p[i]++; if(mx<p[i]+i) mx = p[i] + i, id = i; if(p[i]==i) pre[start[x]+p[i]-2] = 1; if(p[i]+i-1==len) suf[start[x+1]-p[i]+1] = 1; } } ll qu(int x) { ll sum = 0; int p = 0,i; for(i=start[x];i<start[x+1];i++) { int t = s[i] - 'a'; if(!tr[p][t]) break; p = tr[p][t]; if(suf[i+1]==1||i+1==start[x+1]) sum += 1LL*vis[p]; } if(i==start[x+1]) sum += 1LL*qian[p]; return sum; } int main() { int n; while(~scanf("%d",&n)) { int len ; init(); for(int i=1;i<=n;i++) { scanf("%d%s",&len,s+start[i]); start[i+1] = start[i] + len; manacher(i); trie(i); } ll ans = 0; for(int i=1;i<=n;i++) { ans += qu(i); } printf("%lld\n",ans); } }