作为一枚懒人我怎么可能自己写那咕咕咕
这个博客挺好哒
然后回文树实际是可以可持久化哒 (什么不能啊 / xyx)
我们可以把 get_fail 那一部分用数组存下来, 然后可持久化这个数组即可
就先不仔细研究这个玩意了吧咕咕咕
模板 (UOJ#103. [APIO2014] Palindromes)
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<string>
- #include<algorithm>
- #include<cctype>
- #include<cmath>
- #include<cstdlib>
- #include<queue>
- #include<ctime>
- #include<vector>
- #include<set>
- #include<map>
- #include<stack>
- using namespace std;
- int n,fail[300100],son[300100][30],ans[300100],len[300100],cnt,last;
- long long Ans;
- char s[300100];
- inline void new_node(int x){len[++cnt]=x;ans[cnt]=0;}
- inline int get_fail(int x,int n){
- while(s[n]!=s[n-len[x]-1])x=fail[x];
- return x;
- }
- inline void build(){
- for(int i=1;i<=n;i++){
- int x=s[i]-'a',now=get_fail(last,i);
- if(!son[now][x]){
- new_node(len[now]+2);
- fail[cnt]=son[get_fail(fail[now],i)][x];
- son[now][x]=cnt;
- }
- last=son[now][x];
- ans[last]++;
- }
- }
- int main(){
- scanf("%s",s+1);
- n=strlen(s+1);
- cnt--;
- new_node(0),new_node(-1);
- fail[0]=1;
- last=0;
- build();
- for(int i=cnt;i>=0;i--)ans[fail[i]]+=ans[i];
- for(int i=0;i<=cnt;i++)Ans=max(Ans,(long long)len[i]*ans[i]);
- cout<<Ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2956106.html