#hash，trie#洛谷 3449 PAL-Palindromes

本文主要是介绍#hash，trie#洛谷 3449 PAL-Palindromes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给出$n$个回文串$s1,s2,\dots ,sn$，求如下二元组$(i,j)$的个数$si+sj$仍然是回文串。

---

分析

若要两个回文串相连后仍是回文串，那回文串$si$一定是 $sj(leni<=lenj)$的循环节(可以相等，每个回文串自己+自己肯定是个回文串)，是循环节也就是前缀，先用Trie树得出一个串上每个点的前缀情况，再通过Hash判断是否为其循环节，这样得出所有$len[i]<=len[j]$的满足条件的$(si,sj)$,同样也有$(sj,si)$答案$\ast =2$ ，但是每个$(i,i)$仅有一个，这样多了$n$，所以还要减掉$n$

---

代码

#include <cstdio>
#define N 2000001
unsigned long long h[N],hp[N]; char s[N];
int trie[N][26],belong[N],end[N],len[N],n;//字符串总长度不超过n，所以字符数也不会超过n
int in(){int ans=0; char c=getchar();while (c<48||c>57) c=getchar();while (c>47&&c<58) ans=ans*10+c-48,c=getchar();return ans;
}
int main(){hp[0]=1; for (register int i=1;i<N;i++) hp[i]=hp[i-1]*131;n=in(); int tot=0; unsigned long long ans=0;for (register int i=1;i<=n;i++){len[i]=len[i-1]+in(); int p=0; unsigned long long v=0ll;//前缀和随便搞搞for (register int j=len[i-1];j<len[i];j++){s[j]=getchar();if (!trie[p][s[j]-97]) trie[p][s[j]-97]=++tot;//插入新的节点p=trie[p][s[j]-97]; v=v*131+s[j]-96;}end[p]++; belong[p]=i; h[i]=v;//记录结束位置和哈希值}for (register int i=1,p=0;i<=n;i++,p=0)for (register int j=len[i-1];j<len[i];j++){p=trie[p][s[j]-97];if (end[p]&&h[belong[p]]*hp[len[i]-len[i-1]]+h[i]==h[i]*hp[len[belong[p]]-len[belong[p]-1]]+h[belong[p]]) ans+=end[p];//是循环节}return !printf("%llu",(ans<<1)-n);//(i,j)+(j,i)-(i,i)
}

这篇关于#hash，trie#洛谷 3449 PAL-Palindromes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---