学习链接：http://axuhongbo.top/tree/
/*---------------------------------------------
1.len[i]表示编号为i的节点表示的回文串的长度（一个节点表示一个回文串）
2.next[i][c]表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（和字典树类似）。
3.fail[i]表示节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串（和AC自动机类似）。
4.cnt[i]表示节点i表示的本质不同的串的个数（从根节点到当前节点形成的字符串的出现次数）
5.num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。（以i为最终节点，往前形成的子串中是回文串的个数。举个例子：babbab,ba是一个,bab是一个。babbba又是一个，所以当num[i]表示以b为结尾的时候，num[i]=3）
6.last指向新添加一个字母后所形成的最长回文串表示的节点。
7.S[i]表示第i次添加的字符（一开始设S[0] = -1（可以是任意一个在串S中不会出现的字符））。
8.p表示添加的节点个数。
9.n表示添加的字符个数。
------------------------------------*/
题目大意：让你求给定的字符串中最长的回文字符子串。
具体思路：每插入一个字符，求插入的以这个字符结尾形成的最长的回文子串就可以了。
AC代码：
1 #include<iostream> 2 #include<stack> 3 #include<cstring> 4 #include<iomanip> 5 #include<stdio.h> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 # define ll long long 10 # define inf 0x3f3f3f3f 11 const int maxn = 2e5+100; 12 char str[maxn]; 13 struct Palindromic_Tree 14 { 15 int nex[maxn][30]; 16 int fail[maxn]; 17 ll cnt[maxn]; 18 int num[maxn]; 19 int len[maxn]; 20 int s[maxn]; 21 int last; 22 int n; 23 int p; 24 int newnode(int l) 25 { 26 for(int i=0; i<30; i++) 27 nex[p][i]=0; 28 cnt[p]=0; 29 num[p]=0; 30 len[p]=l; 31 return p++; 32 } 33 void init() 34 { 35 p=0; 36 newnode(0); 37 newnode(-1); 38 last=0; 39 n=0; 40 s[n]=-1; 41 fail[0]=1; 42 } 43 int getfail(int x) 44 { 45 while(s[n-len[x]-1]!=s[n]) 46 x=fail[x]; 47 return x; 48 } 49 void add(int t,int c) 50 { 51 c-=‘a‘; 52 s[++n]=c; 53 int cur=getfail(last); 54 // cout<<t<<" "<<cur<<endl; 55 if(!nex[cur][c]) 56 { 57 int now=newnode(len[cur]+2); 58 fail[now]=nex[getfail(fail[cur])][c]; 59 // cout<<cur<<" "<<fail[cur]<<endl; 60 // cout<<11111<<" "<<getfail(fail[cur])<<endl; 61 nex[cur][c]=now; 62 num[now]=num[fail[now]]+1; 63 } 64 last=nex[cur][c]; 65 cnt[last]++; 66 } 67 void cont() 68 { 69 for(int i=p-1; i>=0; i--) 70 cnt[fail[i]]+=cnt[i]; 71 } 72 } q; 73 int main() 74 { 75 int T; 76 scanf("%d",&T); 77 while(~scanf("%s",str)) 78 { 79 int maxx=0; 80 int len=strlen(str); 81 q.init(); 82 for(int i=0; i<len; i++) 83 { 84 q.add(i,str[i]); 85 maxx=max(q.len[q.last],maxx); 86 } 87 printf("%d\n",maxx); 88 } 89 return 0; 90 }
题目大意：给你一个字符串，让你求这个字符串中本质不同的回文串的个数（长度不同，或者长度相同回文串排布不完全相同）。
具体思路：回文树中p-2就是本质不同的回文串的个数，因为如果有重复的就一定能用形成的回文树表示。
AC代码：
1 #include<iostream> 2 #include<stack> 3 #include<cstring> 4 #include<iomanip> 5 #include<stdio.h> 6 #include<algorithm> 7 #include<cmath> 8 using namespace std; 9 # define ll long long 10 # define inf 0x3f3f3f3f 11 const int maxn = 2e5+100; 12 char str[maxn]; 13 struct Palindromic_Tree 14 { 15 int nex[maxn][30]; 16 int fail[maxn]; 17 ll cnt[maxn]; 18 int num[maxn]; 19 int len[maxn]; 20 int s[maxn]; 21 int last; 22 int n; 23 int p; 24 int newnode(int l) 25 { 26 for(int i=0; i<30; i++) 27 nex[p][i]=0; 28 cnt[p]=0; 29 num[p]=0; 30 len[p]=l; 31 return p++; 32 } 33 void init() 34 { 35 p=0; 36 newnode(0); 37 newnode(-1); 38 last=0; 39 n=0; 40 s[n]=-1; 41 fail[0]=1; 42 } 43 int getfail(int x) 44 { 45 while(s[n-len[x]-1]!=s[n]) 46 x=fail[x]; 47 return x; 48 } 49 void add(int t,int c) 50 { 51 c-=‘a‘; 52 s[++n]=c; 53 int cur=getfail(last); 54 // cout<<t<<" "<<cur<<endl; 55 if(!nex[cur][c]) 56 { 57 int now=newnode(len[cur]+2); 58 fail[now]=nex[getfail(fail[cur])][c]; 59 // cout<<cur<<" "<<fail[cur]<<endl; 60 // cout<<11111<<" "<<getfail(fail[cur])<<endl; 61 nex[cur][c]=now; 62 num[now]=num[fail[now]]+1; 63 } 64 last=nex[cur][c]; 65 cnt[last]++; 66 } 67 void cont() 68 { 69 for(int i=p-1; i>=0; i--) 70 cnt[fail[i]]+=cnt[i]; 71 } 72 } q; 73 int main() 74 { 75 int T; 76 scanf("%d",&T); 77 while(~scanf("%s",str)) 78 { 79 int maxx=0; 80 int len=strlen(str); 81 q.init(); 82 for(int i=0; i<len; i++) 83 { 84 q.add(i,str[i]); 85 maxx=max(q.len[q.last],maxx); 86 } 87 printf("%d\n",maxx); 88 } 89 return 0; 90 }
原文：https://www.cnblogs.com/letlifestop/p/10397314.html