回文树(回文自动机PAM)小结
2024-09-02 20:21:26
边写边更新，大概会把回文树总结在一个博客里吧...
回文树的功能
假设我们有一个串S，S下标从0开始，则回文树能做到如下几点：
1.求串S前缀0~i内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）
2.求串S内每一个本质不同回文串出现的次数
3.求串S内回文串的个数（其实就是1和2结合起来）
4.求以下标i结尾的回文串的个数
每个变量的含义
1.len[i]表示编号为i的节点表示的回文串的长度（一个节点表示一个回文串）
2.next[i][c]表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号（和字典树类似）。
3.fail[i]表示节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串（和AC自动机类似）。
4.cnt[i]表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
5.num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
6.last指向新添加一个字母后所形成的最长回文串表示的节点。
7.S[i]表示第i次添加的字符（一开始设S[0] = -1（可以是任意一个在串S中不会出现的字符））。
8.p表示添加的节点个数。
9.n表示添加的字符个数。
板子（来源：poursoul ）
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 100005 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
例题
1. ural1960. Palindromes and Super Abilities
题意
给出一个字符串，输出前 i 个字符中有多少个回文串。
题解
每次加入新的字符后输出 p-2 即可（减去两棵树的根节点）
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 100005 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int next[MAXN][N] ;//next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !next[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 next[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = next[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
64
65 char str[MAXN];
66 ll ans=0;
67
68 int main()
69 {
70 scanf("%s",str);
71 int len=strlen(str);
72 pt.init();
73 for(int i=0;i<len;i++) pt.add(str[i]),printf("%d ",pt.p-2);
74 return 0;
75 }
2. 2014-2015 ACM-ICPC, Asia Xian G The Problem to Slow Down You
题意
给定两个字符串A和B，问A中的每个回文串在B中一共出现了多少次
题解
对A和B分别建回文树，然后对回文树的两棵奇偶树分别跑一下dfs就好了
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 200005 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pa,pb;
64
65 char str1[MAXN];
66 char str2[MAXN];
67 ll ans=0;
68
69 void dfs(int a,int b)
70 {
71 for(int i=0;i<N;i++){
72 if(pa.nt[a][i]&&pb.nt[b][i]){
73 ans+=pa.cnt[pa.nt[a][i]]*1ll*pb.cnt[pb.nt[b][i]];
74 dfs(pa.nt[a][i],pb.nt[b][i]);
75 }
76 }
77 }
78
79 int main()
80 {
81 int t;
82 scanf("%d",&t);
83 int tt=0;
84 while(t--){
85 scanf("%s%s",str1,str2);
86 int len1=strlen(str1);
87 int len2=strlen(str2);
88 pa.init();
89 pb.init();
90 for(int i=0;i<len1;i++) pa.add(str1[i]);
91 pa.count();
92 for(int i=0;i<len2;i++) pb.add(str2[i]);
93 pb.count();
94 ans=0;
95 dfs(0,0);
96 dfs(1,1);
97 printf("Case #%d: ",++tt);
98 printf("%lld\n",ans);
99 }
100 return 0;
101 }
题意
给出一棵树，每棵树给出该节点的元素和其父亲编号，求出这棵树所有回文串的长度*出现的次数。
题解
用邻接表表示这棵树，把回文树中的last变成last数组按深度存储last的值，get_fail部分将last变成last[deep−1]去查找这个回文串的匹配位置。用sum[x]记录结点x的贡献，插入的x如果是新结点，那么sum[now]的值就是sum[fail[now]]+len[now]，失配部分的贡献加上新产生的串的长度。按邻接表dfs插入每个元素，加入回文树后答案加上当前位置的贡献。
这个题有个提示很重要，没看到找了一早上爆栈的原因....如果爆栈了，记得加上这句
代码
1 #pragma comment(linker, "/STACK:102400000,102400000")
2 #include<iostream>
3 #include<cstdio>
4 #include<cstring>
5 #define max(a,b) ((a)>(b)?(a):(b))
6 #define ll long long
7 using namespace std;
8
9 const int MAXN = 2001000 ;
10 const int N = 30 ;
11 ll ans=0;
12
13 struct Edge{
14 int to,nt;
15 }edge[MAXN];
16
17 int head[MAXN],tot;
18
19 void addedge(int u,int v)
20 {
21 edge[tot].to=v;
22 edge[tot].nt=head[u];
23 head[u]=tot++;
24 }
25
26 struct Palindromic_Tree {
27 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
28 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
29 int len[MAXN] ;//表示节点i表示的回文串的长度
30 int S[MAXN] ;//存放添加的字符
31 int last[MAXN] ;//指向上一个字符所在的节点，方便下一次add
32 ll sum[MAXN];
33 int n ;//字符数组指针
34 int p ;//节点指针
35
36 int newnode ( int l ) {//新建节点
37 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
38 len[p] = l ;
39 return p ++ ;
40 }
41
42 void init () {//初始化
43 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
44 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
45 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
46 last[0] = 0 ;
47 n = 0 ;
48 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
49 fail[0] = 1 ;
50 }
51
52 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
53 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
54 return x ;
55 }
56
57 void add ( int c , int x ) {
58 c -= 'a' ;
59 n = x ;
60 S[n] = c ;
61 int cur = get_fail ( last[n-1] ) ;//通过上一个回文串找这个回文串的匹配位置
62 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
63 int now = newnode ( len[cur] + 2 ) ;//新建节点
64 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
65 nt[cur][c] = now ;
66 sum[now]=sum[fail[now]]+len[now];
67 }
68 last[n] = nt[cur][c] ;
69 ans+=sum[last[n]];
70 }
71 }pt;
72
73 char s[MAXN];
74
75 void dfs(int u,int x)
76 {
77 for(int i=head[u];~i;i=edge[i].nt){
78 int v=edge[i].to;
79 pt.add(s[v],x);
80 dfs(v,x+1);
81 }
82 }
83
84 int main()
85 {
86 int t;
87 scanf("%d",&t);
88 while(t--){
89 tot=0;
90 memset(head,-1,sizeof(head));
91 pt.init();
92 int n;
93 scanf("%d",&n);
94 for(int i=1;i<=n;i++){
95 char ch[10];
96 int x;
97 scanf("%s%d",ch,&x);
98 s[i]=ch[0];
99 addedge(x,i);
100 }
101 ans=0;
102 dfs(0,1);
103 printf("%lld\n",ans);
104 }
105 return 0;
106 }
4. Skr
题意
给定一个字符串，求每个回文串的数值之和对mod求余，mod=1e9+7;
题解
一开始想的是每次加入字符 s[x] (从1开始)形成的新的回文串len[now]是它的长度，所以这个回文串的数值就是从x-len[now]到x-1，那么只要遍历算出这个串的数值就好了，然后就愉快的 t 了。
那么就要优化他，空间也得优化，不然很容易爆，因为是数字0~9，所以next数组第二维只要开10就好了，这样就不会爆内存了。
对于时间优化，可以用a数组存s的前缀数值，b数组存pow(10，i )，那么对于x-len[now]到x-1这一段的值就是a[x]-a[x-len[now]]*b[len[now]]（记得取模^_^），类似于哈希的做法。这个地方一开始写成了b[x-len[now]]（我真是憨憨），因为这一段的长度是len[now]，他们之前的差的倍数就是pow(10，len[now]）倍。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 2e6+10 ;
9 const int N = 10 ;
10 const ll mod = 1e9+7 ;
11 char str[MAXN];
12 ll ans=0;
13 ll a[MAXN],b[MAXN];
14
15 struct Palindromic_Tree {
16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
18 int len[MAXN] ;//表示节点i表示的回文串的长度
19 int S[MAXN] ;//存放添加的字符
20 int last ;//指向上一个字符所在的节点，方便下一次add
21 int n ;//字符数组指针
22 int p ;//节点指针
23
24 int newnode ( int l ) {//新建节点
25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ,int x ) {
46 c -= '0' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 ans+=((a[x]-a[x-len[now]]*b[len[now]]%mod)%mod+mod)%mod;
54 ans%=mod;
55 }
56 last = nt[cur][c] ;
57 }
58
59 }pt;
60
61 int main()
62 {
63 scanf("%s",str);
64 int len=strlen(str);
65 pt.init();
66 b[0]=1;
67 for(ll i=1;i<=len;i++) {
68 a[i]=a[i-1]*10+str[i-1]-'0';
69 a[i]%=mod;
70 b[i]=b[i-1]*10%mod;
71 }
72 for(int i=0;i<len;i++) pt.add(str[i],i+1);
73 printf("%lld\n",ans);
74 return 0;
75 }
题意
给定一个字符串，求每个回文串中不同的字母的个数和。
题解
先建一棵回文树，然后奇偶树分别从根节点开始dfs，用vis数组标记字符是否出现过，遇到没出现过的字符，个数 y 就+1。对于每个结点 x 更新答案ans，也就是ans+=y*cnt[next[x][i]]。根据前边的变量的含义：4.cnt[i]表示节点 i 表示的本质不同的串的个数。也就是不同字符的个数*以结点 x 表示的不同的串的个数。然后继续往下找下一个结点。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 3e5+10 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
64
65 char str[MAXN];
66 ll ans=0;
67 bool vis[N];
68
69 void dfs(int x,int y)
70 {
71 for(int i=0;i<N;i++){
72 if(pt.nt[x][i]){
73 if(!vis[i]){
74 vis[i]=1;
75 y++;
76 ans+=y*pt.cnt[pt.nt[x][i]];
77 dfs(pt.nt[x][i],y);
78 vis[i]=0;
79 y--;
80 }
81 else{
82 ans+=y*pt.cnt[pt.nt[x][i]];
83 dfs(pt.nt[x][i],y);
84 }
85 }
86 }
87 }
88
89 int main()
90 {
91 scanf("%s",str);
92 int len=strlen(str);
93 pt.init();
94 for(int i=0;i<len;i++) pt.add(str[i]);
95 pt.count();
96 dfs(0,0);
97 memset(vis,0,sizeof(vis));
98 dfs(1,0);
99 printf("%lld\n",ans);
100 return 0;
101 }
题意
对于一个给定的字符串，他是加密的，要求解密后的字符串的以每个位置为结尾的回文子串个数。若第 i (i≥1) 个位置的答案是 k，第 i+1 个字符读入时的ASCII 码为 c，则第 i+1 个字符实际的 ASCII 码为 (c−97+k)mod26+97。这个题有毒，题意看了3遍都是错的，让我样例都写不出来。他的k是以上一个字符为结尾的回文串的个数，而不是上一个字符。
题解
就是板子题，每次输出上边含义中的（5.num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。）num[last]，并且更新k为num[last]，因为last为新加入回文树的元素的编号。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 5e5+10 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
64
65 char str[MAXN];
66 ll ans=0;
67
68 int main()
69 {
70 scanf("%s",str);
71 int len=strlen(str);
72 int k=0;
73 pt.init();
74 for(int i=0;i<len;i++) {
75 str[i]=(str[i]+k-97)%26+97;
76 pt.add(str[i]);
77 printf("%d ",pt.num[pt.last]);
78 k=pt.num[pt.last];
79 }
80 return 0;
81 }
7. P5555 秩序魔咒
题意
给定两个字符串，求最长的，不同的，且在两个字符串中都出现了的回文串长度和个数。
题解
和第 2 题有点类似，对A和B分别建回文树，然后对回文树的两棵奇偶树分别跑一下dfs，用len[now]更新最长长度，如果出现长度一样的更新答案+1。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 3e5+10 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pa,pb;
64
65 char s[MAXN];
66 char t[MAXN];
67 ll ans=0,p=0;
68
69 void dfs(int a,int b)
70 {
71 for(int i=0;i<N;i++){
72 int x=pa.nt[a][i];
73 int y=pb.nt[b][i];
74 if(x&&y){
75 int q=pa.len[x];
76 if(q>p) p=q,ans=0;
77 if(q==p){
78 ans++;
79 }
80 dfs(x,y);
81 }
82 }
83 }
84
85 int main()
86 {
87 int len1,len2;
88 scanf("%d%d",&len1,&len2);
89 scanf("%s%s",s,t);
90 pa.init();
91 pb.init();
92 for(int i=0;i<len1;i++) pa.add(s[i]);
93 for(int i=0;i<len2;i++) pb.add(t[i]);
94 pa.count();
95 pb.count();
96 dfs(0,0);
97 dfs(1,1);
98 printf("%lld %lld\n",p,ans);
99 return 0;
100 }
题意
给定一个字符串，求字符串中回文串的长度*出现次数最大值。
题解
建一棵回文树，遍历每个结点，用 cnt[i]*len[i] 更新ans的最大值。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 100005 ;
9 const int N = 26 ;
10
11 struct Palindromic_Tree {
12 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 int len[MAXN] ;//表示节点i表示的回文串的长度
17 int S[MAXN] ;//存放添加的字符
18 int last ;//指向上一个字符所在的节点，方便下一次add
19 int n ;//字符数组指针
20 int p ;//节点指针
21
22 int newnode ( int l ) {//新建节点
23 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
64
65 char str[MAXN];
66 ll ans=0;
67
68 int main()
69 {
70 scanf("%s",str);
71 int len=strlen(str);
72 pt.init();
73 for(int i=0;i<len;i++) pt.add(str[i]);
74 pt.count();
75 for(int i=2;i<pt.p;i++) ans=max(ans,1ll*pt.cnt[i]*pt.len[i]);
76 printf("%lld\n",ans);
77 return 0;
78 }
题意
给定一个字符串，找出最长的回文串，长度是4的倍数，且回文串的前半部分和后半部分分别是个回文串。
题解
本来以为是两个连着的相同的回文串，结果发现连起来的串也得是回文串...（我可真是读题bug姬
hash的做法：
类似于第4题str，加入元素是判断如果当前这个回文串的长度可以被4整除，那么就可以用hash比较前半段和后半段是否相等，相等的话更新答案。
利用fail数组：
构造一个trans数组，记录小于等于当前节点长度一半的最长回文后缀。每次新建立一个节点的时候，如果他表示的回文串长度小于等于2，那么trans[now]=fail[now]，否则从 trans[父亲] 开始走fail，直到某一个节点所表示的回文串的两侧都能扩展这个字符并且拓展后的长度小于等于他表示的回文串的一半。最后再判断一下当前回文串的长度是否是4的倍数并且 trans[now] 表示的回文串的长度是当前回文串的一半，并更新答案。
代码
hash：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 #define ull unsigned long long
7 using namespace std;
8
9 const int MAXN = 5e5+10 ;
10 const int N = 26 ;
11 char str[MAXN];
12 ll ans=0;
13 ull a[MAXN],b[MAXN];
14 const ull base = 131;
15
16 struct Palindromic_Tree {
17 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
18 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
19 int len[MAXN] ;//表示节点i表示的回文串的长度
20 int S[MAXN] ;//存放添加的字符
21 int last ;//指向上一个字符所在的节点，方便下一次add
22 int n ;//字符数组指针
23 int p ;//节点指针
24
25 int newnode ( int l ) {//新建节点
26 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
27 len[p] = l ;
28 return p ++ ;
29 }
30
31 void init () {//初始化
32 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
33 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
34 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
35 last = 0 ;
36 n = 0 ;
37 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
38 fail[0] = 1 ;
39 }
40
41 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
42 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
43 return x ;
44 }
45
46 void add ( int c ,int x ) {
47 c -= '0' ;
48 S[++ n] = c ;
49 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
50 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
51 int now = newnode ( len[cur] + 2 ) ;//新建节点
52 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
53 nt[cur][c] = now ;
54 if(len[now]%4==0){
55 ull xx=len[now]/2;
56 ull pp=(a[x-xx]-a[x-len[now]])*b[xx];
57 ull qq=a[x]-a[x-xx];
58 if(pp==qq) ans=max(ans,len[now]);
59 }
60 }
61 last = nt[cur][c] ;
62 }
63 }pt;
64
65 int main()
66 {
67 int len;
68 scanf("%d",&len);
69 scanf("%s",str);
70 pt.init();
71 b[0]=1;
72 for(ll i=1;i<=len;i++) {
73 a[i]=a[i-1]*base+str[i-1];
74 b[i]=b[i-1]*base;
75 }
76 for(int i=0;i<len;i++) pt.add(str[i],i+1);
77 printf("%lld\n",ans);
78 return 0;
79 }
fail：
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 #define ull unsigned long long
7 using namespace std;
8
9 const int MAXN = 5e5+10 ;
10 const int N = 26 ;
11 char str[MAXN];
12 int trans[MAXN];
13 int ans=0;
14
15 struct Palindromic_Tree {
16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
18 int len[MAXN] ;//表示节点i表示的回文串的长度
19 int S[MAXN] ;//存放添加的字符
20 int last ;//指向上一个字符所在的节点，方便下一次add
21 int n ;//字符数组指针
22 int p ;//节点指针
23
24 int newnode ( int l ) {//新建节点
25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 if(len[now]>2){
54 int x=trans[cur];
55 while(S[n-len[x]-1]!=S[n]||(len[x]+2)*2>len[now]) x=fail[x];
56 trans[now]=nt[x][c];
57 }
58 else trans[now]=fail[now];
59 if(len[trans[now]]*2==len[now]&&len[now]%4==0) ans=max(ans,len[now]);
60 }
61 last = nt[cur][c] ;
62 }
63 }pt;
64
65 int main()
66 {
67 int len;
68 scanf("%d",&len);
69 scanf("%s",str);
70 pt.init();
71 for(int i=0;i<len;i++) pt.add(str[i]);
72 printf("%d\n",ans);
73 return 0;
74 }
10. P4762 [CERC2014]Virus synthesis
题意
初始有一个空串，利用下面的操作构造给定串 S。
1、串开头或末尾加一个字符
2、串开头或末尾加一个该串的逆串
求最小化操作数，∣S∣≤1e5 。
题解
肯定能想到套娃找回文串可以执行2更多的，问题是要如何找。这个就可以想上一个题的fail数组的做法那样，构造一个trans数组，记录小于等于当前节点长度一半的最长回文后缀。每次新建立一个节点的时候，如果他表示的回文串长度小于等于2，那么trans[now]=fail[now]，否则从 trans[父亲] 开始走fail，直到某一个节点所表示的回文串的两侧都能扩展这个字符并且拓展后的长度小于等于他表示的回文串的一半。
用dp[i]表示转移到 i 代表的回文串的最少的需要次数。因为要执行操作2，执行后的串肯定是偶数串，所以如果当前回文串的长度为偶数，那么就可以考虑两种情况：
一种是直接从上一个回文串前后都加一个字符，这就相当于是前一半加了字符之后再翻转，相当于步数+1，dp[now]=dp[cur]+1。
另一种是考虑加入新字符之后左半边会不会有 ‘套娃’ ，也就是可以将左半边的某个回文子串先添加一半再翻转（这里就用到了trans数组，当然是越长的回文子串越好了），然后剩余的部分用操作1继续添加，最后把左半边用操作2形成整个串，也就是dp[now]=dp[trans[now]]+(len[now] / 2-len[trans[now]])+1。每次新建结点的时候都要更新答案ans，因为dp数组记录的是长度为len[now]的串的最少步数，所以要用dp[now]+length-len[now]来更新。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 #define ull unsigned long long
7 using namespace std;
8
9 const int MAXN = 1e5+10 ;
10 const int N = 26 ;
11 char str[MAXN];
12 int dp[MAXN],trans[MAXN];
13 int ans=0;
14
15 struct Palindromic_Tree {
16 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
17 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
18 int len[MAXN] ;//表示节点i表示的回文串的长度
19 int S[MAXN] ;//存放添加的字符
20 int last ;//指向上一个字符所在的节点，方便下一次add
21 int n ;//字符数组指针
22 int p ;//节点指针
23
24 int newnode ( int l ) {//新建节点
25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];
42 return x ;
43 }
44
45 void add ( int c ,int length) {
46 c -= 'A' ;
47 S[++ n] = c ;
48 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 int now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 if(len[now]>2){
54 int x=trans[cur];
55 while(S[n-len[x]-1]!=S[n]||(len[x]+2)*2>len[now]) x=fail[x];
56 trans[now]=nt[x][c];
57 }
58 else trans[now]=fail[now];
59 dp[now]=len[now];
60 if(len[now]%2==0){
61 dp[now]=min(dp[now],dp[cur]+1);
62 dp[now]=min(dp[now],dp[trans[now]]+1+(len[now]/2-len[trans[now]])); //从上一个结点添加+1或者从fail那开始添加到一半然后翻转
63 ans=min(ans,dp[now]+length-len[now]); //dp[now]是当前长度回文串的最少步数，总步数是长度减当前回文串长度加步数。
64 }
65 }
66 last = nt[cur][c] ;
67 }
68 }pt;
69
70 int main()
71 {
72 int t;
73 scanf("%d",&t);
74 while(t--){
75 memset(trans,0,sizeof(trans));
76 memset(dp,0,sizeof(dp));
77 scanf("%s",str);
78 int len=strlen(str);
79 pt.init();
80 ans=len;
81 dp[0]=1;
82 for(int i=0;i<len;i++) pt.add(str[i],len);
83 printf("%d\n",ans);
84 }
85 return 0;
86 }
11. #2565. 最长双回文串
题意
求连续的两个回文串的最长长度和。
题解
bzoj可算好了，结果发现洛谷也有这个题......
回文树中len数组的含义是当前节点所表示的最长回文串的长度，那么可以考虑建两个回文树，一个正着插入字符串，一个倒着。新增一个sum数组，每次加入新的字符之后记录下当前字符为结尾的最长回文串的长度，（len数组只是新建结点所表示的长度），最后只要用sum1 [ i ] + sum2 [ length - i ] 来更新最大值就好了。有一个地方要注意的是，例如串aba，这样答案就会是3，所以要加一个判断条件，让sum1和sum2都得大于0才能用于更新。
为什么不能只建一棵回文树呢，因为sum[ i ] + sum [ i - sum [ i ] ] 这样求得并不是最优，比如 caaaacaa，这个字符串如果一棵回文树求就会被分为 aa和aacaa，caaaac和aa为什么不行呢，因为以最后一个a为结尾的最长回文串的长度是5 ，aacaa啊..... 倒着建一个回文树就可以解决这个问题了（逃
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 2e6+10 ;
9 const int N = 26 ;
10 int ans=0;
11
12 struct Palindromic_Tree {
13 int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
14 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
15 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
16 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
17 int len[MAXN] ;//表示节点i表示的回文串的长度
18 int S[MAXN] ;//存放添加的字符
19 int sum[MAXN];
20 int last ;//指向上一个字符所在的节点，方便下一次add
21 int n ;//字符数组指针
22 int p ;//节点指针
23
24 int newnode ( int l ) {//新建节点
25 for ( int i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
26 cnt[p] = 0 ;
27 num[p] = 0 ;
28 len[p] = l ;
29 return p ++ ;
30 }
31
32 void init () {//初始化
33 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
34 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
35 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
36 last = 0 ;
37 n = 0 ;
38 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
39 fail[0] = 1 ;
40 }
41
42 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
43 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];//直到某一个节点所表示的回文串的两侧都能扩展这个字符
44 return x ;
45 }
46
47 void add ( int c ) {
48 c -= 'a' ;
49 S[++ n] = c ;
50 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
51 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
52 int now = newnode ( len[cur] + 2 ) ;//新建节点
53 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
54 nt[cur][c] = now ;
55 num[now] = num[fail[now]] + 1 ;
56 }
57 last = nt[cur][c] ;
58 sum[n]=len[last];
59 cnt[last] ++ ;
60 }
61
62 void count () {
63 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
64 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
65 }
66 }pt1,pt2;
67
68 char str[MAXN];
69
70 int main()
71 {
72 scanf("%s",str);
73 int len=strlen(str);
74 pt1.init();
75 pt2.init();
76 for(int i=0;i<len;i++) pt1.add(str[i]);
77 for(int i=len-1;i>=0;i--) pt2.add(str[i]);
78 for(int i=1;i<=len;i++){
79 if(pt1.sum[i]&&pt2.sum[len-i]) ans=max(ans,pt1.sum[i]+pt2.sum[len-i]);
80 }
81 printf("%d\n",ans);
82 return 0;
83 }
12. #2160. 拉拉队排练
题意
求长度最长且为奇数的前 k 个回文串的长度之积，对19930726取模，如果奇数回文串个数小于k，那么输出-1。
题解
建一棵回文树，求len和cnt数组，按照len数组由大到小排个序，（可以直接用计数排序），然后找前k个长度为奇数的串，将长度相乘。这个地方要用快速幂。也就是直接记录每个长度有几个回文串，然后直接快速幂。
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const ll MAXN = 1e6+10 ;
9 const ll N = 26 ;
10
11 struct Palindromic_Tree {
12 ll nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
13 ll fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
14 ll cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
15 ll num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
16 ll len[MAXN] ;//表示节点i表示的回文串的长度
17 ll S[MAXN] ;//存放添加的字符
18 ll last ;//指向上一个字符所在的节点，方便下一次add
19 ll n ;//字符数组指针
20 ll p ;//节点指针
21
22 ll newnode ( ll l ) {//新建节点
23 for ( ll i = 0 ; i < N ; ++ i ) nt[p][i] = 0 ;
24 cnt[p] = 0 ;
25 num[p] = 0 ;
26 len[p] = l ;
27 return p ++ ;
28 }
29
30 void init () {//初始化
31 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
32 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
33 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
34 last = 0 ;
35 n = 0 ;
36 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
37 fail[0] = 1 ;
38 }
39
40 ll get_fail ( ll x ) {//和KMP一样，失配后找一个尽量最长的
41 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];//直到某一个节点所表示的回文串的两侧都能扩展这个字符
42 return x ;
43 }
44
45 void add ( ll c ) {
46 c -= 'a' ;
47 S[++ n] = c ;
48 ll cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
49 if ( !nt[cur][c] ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
50 ll now = newnode ( len[cur] + 2 ) ;//新建节点
51 fail[now] = nt[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针，以便失配后跳转
52 nt[cur][c] = now ;
53 num[now] = num[fail[now]] + 1 ;
54 }
55 last = nt[cur][c] ;
56 cnt[last] ++ ;
57 }
58
59 void count () {
60 for ( ll i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
61 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
62 }
63 }pt;
64
65 char str[MAXN];
66 const ll mod=19930726;
67 ll res[MAXN];
68
69 ll quick(ll a,ll b)
70 {
71 ll ans=1;
72 a%=mod;
73 while(b){
74 if(b&1) ans*=a,ans%=mod;
75 b>>=1;
76 a*=a;
77 a%=mod;
78 }
79 return ans%mod;
80 }
81
82 int main()
83 {
84 ll n,k;
85 scanf("%lld%lld",&n,&k);
86 scanf("%s",str);
87 ll len=n;
88 pt.init();
89 for(ll i=0;i<len;i++) pt.add(str[i]);
90 pt.count();
91 for(ll i=2;i<pt.p;i++) res[pt.len[i]]+=pt.cnt[i];
92 if(len%2==0) len--;
93 ll ans=1;
94 for(ll i=len;i>=0;i-=2){
95 ans*=quick(i,min(k,res[i]));
96 ans%=mod;
97 k-=min(k,res[i]);
98 if(!k) break;
99 }
100 if(k) printf("-1\n");
101 else printf("%lld\n",ans);
102 return 0;
103 }
题意
给定一个长度为n的小写字母串。问你有多少对相交的回文子串（包含也算相交），结果对51123987取模。
题解
求相交的个数不是很好求，可以将问题转换为所有总的回文串对数减去不相交的回文串个数。正着建一棵回文树可以求出以 s[ i ] 为结尾的回文串个数 ai ，反着建一棵回文树可以求出以 s[ i ] 为起点的回文串个数 bi 。那么不相交的回文串对数就是ai*sum{bi+1,bi+2,...,bi+n} (i=1,2,...,n-1)；
因为内存限制，所以这个题next数组要用邻接表。
参考博客：https://blog.csdn.net/Dacc123/article/details/51354825
代码
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #define max(a,b) ((a)>(b)?(a):(b))
5 #define ll long long
6 using namespace std;
7
8 const int MAXN = 2e6+10 ;
9 const int N = 26 ;
10
11 struct link
12 {
13 int u[MAXN],v[MAXN];
14 int next[MAXN];
15 int head[MAXN];
16 int tot;
17 void init()
18 {
19 memset(head,-1,sizeof(head));
20 tot=0;
21 }
22 void init(int x) {head[x]=-1;}
23 int get(int x,int y)
24 {
25 for(int i=head[x];~i;i=next[i]){
26 if(u[i]==y) return v[i];
27 }
28 return 0;
29 }
30 void insert(int x,int y,int z){
31 u[tot]=y;v[tot]=z;
32 next[tot]=head[x];
33 head[x]=tot++;
34 }
35 };
36
37 struct Palindromic_Tree {
38 ///int nt[MAXN][N] ;//nt指针，nt指针和字典树类似，指向的串为当前串两端加上同一个字符构成
39 int fail[MAXN] ;//fail指针，失配后跳转到fail指针指向的节点
40 int cnt[MAXN] ;//表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）
41 int num[MAXN] ;//表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。
42 int len[MAXN] ;//表示节点i表示的回文串的长度
43 int S[MAXN] ;//存放添加的字符
44 int last ;//指向上一个字符所在的节点，方便下一次add
45 int n ;//字符数组指针
46 int p ;//节点指针
47 link next;
48 int newnode ( int l ) {//新建节点
49 cnt[p] = 0 ;
50 num[p] = 0 ;
51 len[p] = l ;
52 next.init(p);
53 return p ++ ;
54 }
55
56 void init () {//初始化
57 p = 0 ;//0为存储 偶数回文串 树根节点，1为存储 奇数回文串 树根节点
58 newnode ( 0 ) ;/*p==0,偶数回文串树根节点编号为0,len值为0*/
59 newnode ( -1 ) ;/*p==1,奇数回文串树根节点编号为1,len值为-1*/
60 last = 0 ;
61 n = 0 ;
62 S[n] = -1 ;//开头放一个字符集中没有的字符，减少特判
63 fail[0] = 1 ;
64 next.init();
65 }
66
67 int get_fail ( int x ) {//和KMP一样，失配后找一个尽量最长的
68 while ( S[n - len[x] - 1] != S[n] ) x = fail[x];//直到某一个节点所表示的回文串的两侧都能扩展这个字符
69 return x ;
70 }
71
72 int add ( int c ) {
73 c -= 'a' ;
74 S[++ n] = c ;
75 int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
76 if ( !next.get(cur,c) ) {//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
77 int now = newnode ( len[cur] + 2 ) ;//新建节点
78 fail[now] = next.get(get_fail ( fail[cur] ),c);//和AC自动机一样建立fail指针，以便失配后跳转
79 next.insert(cur,c,now);
80 num[now] = num[fail[now]] + 1 ;
81 }
82 last = next.get(cur,c);
83 cnt[last] ++ ;
84 return last;
85 }
86
87 void count () {
88 for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
89 //父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
90 }
91 }pt;
92
93 char str[MAXN];
94 ll ans=0;
95 const ll mod=51123987;
96 int q[MAXN];
97
98 int main()
99 {
100 int n,k;
101 scanf("%d",&n);
102 scanf("%s",str);
103 pt.init();
104 for(int i=0;i<n;i++){
105 int last=pt.add(str[i]);
106 k=pt.num[last];
107 if(i) {
108 q[i]=(q[i-1]+k)%mod;
109 }
110 else q[i]=k%mod;
111 }
112 pt.count();
113 for(int i=2;i<pt.p;i++) ans+=pt.cnt[i],ans%=mod;
114 ans=(ans)*(ans-1)/2;
115 ans%=mod;
116 pt.init();
117 for(int i=n-1;i>=0;i--){
118 int last=pt.add(str[i]);
119 k=pt.num[last];
120 ans=(ans+mod-1ll*k*q[i-1]%mod)%mod;
121 }
122 printf("%lld\n",ans);
123 return 0;
124 }
最新文章
- python课程第二周重点记录
- 【DPM】Deformable Part Models matlab代码在windows下的调试过程
- 汉企学习4个半月的target and plan
- POS管理系统之设备出库
- Block的使用及循环引用的解决
- LINQ——语言级集成查询入门指南(1)
- opennebula 编译日志
- Cocos2d-x项目总结中的一些遇到的问题
- CF Round #354 Div.2
- Linux下一次删除百万文件
- centos7虚拟机设置静态ip
- POJ_1269_Intersecting Lines_求直线交点
- Android 9.0/P http 网络请求的问题
- kafka 心跳和 reblance
- [译]迁移到新的 React Context Api
- hmtl div水平、垂直居中
- python中read()、readline()、readlines()函数
- c++——register关键字、struct类型、bool关键字、三目运算符
- 另类之将ipython notebook嵌入blog方法
- golang 关键字以及简单用法说明
热门文章
- nodejs事件和事件循环详解
- 网络之HTTPS
- python3.6安装教程
- 基础篇-http协议《http 简介、url详解、request》
- 计算起始车站车费问题-JavaScript数组对象写法
- SGA: allocation forcing component growth分析
- 03--Docker 容器和镜像常用命令
- LuoguP5075 [JSOI2012]分零食
- Sgu149 Computer Network
- EL&Filter&Listener:EL表达式和JSTL,Servlet规范中的过滤器,Servlet规范中的监听器,观察着设计模式,监听器的使用,综合案例学生管理系统