回文树

ACM

在网络赛现学回文树。。不过还是赛后出题了。。gg

回文树

概述

回文树是对着一个单串建立的一种处理字符串的数据结构，主要用于计数（回文子串种类及个数）。基本建立思路是建立其前缀的回文树，然后每加上一个字符，统计产生了什么回文。

下图展示了回文树的结构。

对于字符串 abccbab，我们可以建出以下回文树：

实例

红色箭头表示 fail 指针，蓝色箭头表示字符匹配成功会转移的位置。

回文树可以解决的问题

假设我们有一个串$S$，$S$下标从$0$开始，则回文树能做到如下几点：

1.求串$S$前缀$0 - i$内本质不同回文串的个数（两个串长度不同或者长度相同且至少有一个字符不同便是本质不同）

2.求串$S$内每一个本质不同回文串出现的次数

3.求串$S$内回文串的个数（其实就是$1$和$2$结合起来）

4.求以下标$i$结尾的回文串的个数

回文树的结构

首先我们定义一些变量。

1.len[i]表示编号为i的节点表示的回文串的长度（一个节点表示一个回文串）；

2.ch[i][c]表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号。

3.fail[i]表示节点i失配以后跳转到长度小于该串且以该节点表示回文串的最后一个字符结尾的最长回文串表示的节点。

4.ans[i]表示节点i表示的本质不同的串的个数（建树时求出的不是完全的，最后count()函数跑一遍以后才是正确的）

5.num[i]表示以节点i表示的最长回文串的最右端点为回文串结尾的回文串个数。

6.last指向新添加一个字母后所形成的最长回文串表示的节点。

7.S[i]表示第i次添加的字符（一开始设S[0] = -1（可以是任意一个在串S中不会出现的字符））。

8.p表示添加的节点个数。

9.cnt表示添加的字符个数。

回文树模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct PA
{
	int num[maxn],len[maxn],fail[maxn],S[maxn], ch[maxn][maxc];	
	int p,last,cnt, ans[maxn];
	ll tot[maxn];
	
	//tot 表示当前节点表示回文串中的后缀子回文串的个数(包括自己)
	//len 当前节点表示的回文串的长度
	//S 存放添加的字符
	//p节点个数 cnt字符串长度
	
	int newnode(int l){
	    tot[p]=0; num[p]=0; len[p]=l;
	    return p++;
	}
	void init(){
	    p=0; memset(ch,0,sizeof(ch));
	    newnode(0); newnode(-1);
        //添加偶数结点、奇数结点
	    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
	    //开头放一个字符集中没有的字符，减少特判
	}
	int get_fail(int x){ //失配后找一个尽量最长的
	    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
	    return x;
	}
	void add(int c,int pos){ //返回以当前字符结尾的回文串个数
	    S[++cnt]=c;
	    int cur=get_fail(last); //通过上一个回文串找这个回文串的匹配位置
	    if (!ch[cur][c]){
	    	//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
	        int now=newnode(len[cur]+2); // 新建节点
	        fail[now]=ch[get_fail(fail[cur])][c];
	        //建立fail指针，以便失配后跳转
	        ch[cur][c]=now;
            num[now] = num[fail[now]] + 1;
	    }
	    last = ch[cur][c];
	    tot[last]++;
	    ans[pos] = len[last];
	}
    void count()
    {
        for(int i = p - 1; ~i; -- i)
            tot[fail[i]] += tot[i];
    }
};

回文树的应用

UOJ 103 Palindromes

（为什么是这个编号。。）

就是这道题提出了这个算法。

出现次数用 ans[i] ，长度用 len[i] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 300000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
int num[maxn],len[maxn],fail[maxn],S[maxn],ch[maxn][maxc];
char s[maxn];
int p,last,cnt;
ll tot[maxn];
	
int newnode(int l){
    tot[p]=0; num[p]=0; len[p]=l;
    return p++;
}
void init(){
    p=0; memset(ch,0,sizeof(ch));
    newnode(0); newnode(-1);
    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
}
int get_fail(int x){
    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
    return x;
}
void add(int c,int pos){
    S[++cnt]=c;
    int cur=get_fail(last);
    if (!ch[cur][c]){
        int now=newnode(len[cur]+2);
        fail[now]=ch[get_fail(fail[cur])][c];
        ch[cur][c]=now;
    }
    last=ch[cur][c];
    tot[last]++;
}
ll ans()
{
	ll ans = 0;
	for(int i = p - 1; ~i; -- i)
		tot[fail[i]] += tot[i], ans = max(ans, (ll)(len[i] * tot[i]));
	return ans;
}
int main()
{
    scanf("%s",s);
    int n = strlen(s);
    init();
    for(int i = 0; i < n; ++ i)
    	add(s[i] - 'a' + 1, i);
    printf("%lld\n", ans());
	return 0;
}

HDU 3948 The Number of Palindromes

求本质不同的回文串的个数。

板子的来源。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#endif
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
const int MOD = 1e9 + 7;
const int maxn = 100000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
int tot[maxn],num[maxn],len[maxn],fail[maxn],S[maxn],ch[maxn][maxc];
char s[maxn];
int p,last,cnt;
long long ans;
int newnode(int l){
    tot[p]=0; num[p]=0; len[p]=l;
    return p++;
}
void init(){
    p=0; memset(ch,0,sizeof(ch));
    newnode(0); newnode(-1);
    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
}
int get_fail(int x){
    while(S[cnt-len[x]-1]!=S[cnt]) x=fail[x];
    return x;
}
void add(int c,int pos){
    S[++cnt]=c;
    int cur=get_fail(last);
    if (!ch[cur][c]){
        int now=newnode(len[cur]+2);
        fail[now]=ch[get_fail(fail[cur])][c];
        ch[cur][c]=now; ans++;
    }
    last=ch[cur][c];
    tot[last]++;
}
/*
ll ten[maxn];
void bianli(int cur, long long p, int len)
{
	if(cur == 0) //??×óê÷ 
	{
		for(int i = 0; i < 10; i ++)
			if(ch[cur][i])
			{
				ans = (ans + i * 10 % mod + i) % mod;
				bianli(ch[cur][i], i * 10 % mod + i, 2);
			}
		return ;
	}
	if(cur == 1)
	{
		for(int i = 0; i < 10; i ++)
			if(ch[cur][i])
			{
				ans = (ans + i) % mod;
				bianli(ch[cur][i], i, 1);
			}
		return ;
	}
	for(int i = 0; i < 10; i ++)
		if(ch[cur][i])
		{
			ans = (ans + (1ll * i * ten[len + 1] % mod + p * 10 % mod + i) % mod) % mod;
			bianli(ch[cur][i], (1ll * i * ten[len + 1] % mod + p * 10 % mod + i) % mod, len + 2);
		}
}
*/
int main(){
	int T;
	scanf("%d", &T);
	for(int Casen = 1; Casen <= T; ++ Casen)
	{
	    ans = 0;
	    scanf("%s",s);
	    int n = strlen(s);
	    init();
	    //FORP(i,0,n-1) add(s[i]-'0'+1,i);
	    /*
	    ten[0] = 1;
	    for(int i = 1; i <= n + 1; i ++)
	    	ten[i] = ten[i - 1] * 10 % mod;
	    bianli(0, 0, 0);
	    bianli(1, 0, 0);
	    */
	    for(int i = 0; i < n; ++ i)
	    	add(s[i] - 'a' + 1, i);
	    printf("Case #%d: %lld\n", Casen, ans);
	}
	return 0;
}

CodeChef PALPROB Palindromeness

题目链接

求出当前回文串节点的长度的一半的那个回文串所代表的节点。

定义 half 表示长度最长并且长度小于等于当前节点长度一半的回文串所代表的节点 ，half的求法，如果当前点的len=1, half不存在；否则，从构建回文树时的父亲节点（不是fail指针）所代表的那个点的half 开始
暴力跳fail ，直到找到满足条件的点，假设是 pos，当前点的half 就是 trans[pos][当前字符]。

有毒。。把我的板子改飞了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
#include <bits/stdc++.h>
#else
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#endif
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
using namespace std;
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
const int MOD = 1e9 + 7;
const int maxn = 200000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
int num[maxn],len[maxn],fail[maxn],S[maxn],ch[maxn][maxc], hf[maxn], ph[maxn];
char s[maxn];
int p,last,cnt;
ll tot[maxn];
//tot 表示当前节点表示回文串中的后缀子回文串的个数(包括自己)
//len 当前节点表示的回文串的长度
//S 存放添加的字符
//p节点个数 cnt字符串长度
int newnode(int l){
    tot[p]=0; num[p]=0; len[p]=l;
    return p++;
}
void init(){
    p=0; memset(ch,0,sizeof(ch));
    newnode(0); newnode(-1);
    last=0; cnt=0; S[cnt]=-1; fail[0] = hf[0] = 1;
    //开头放一个字符集中没有的字符，减少特判
}
int get_fail(int x){ //和KMP一样，失配后找一个尽量最长的
    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
    return x;
}
void add(int c,int pos){ //返回以当前字符结尾的回文串个数
    S[++cnt]=c;
    int cur=get_fail(last);  //通过上一个回文串找这个回文串的匹配位置
    if (!ch[cur][c]){
    	//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
        int now=newnode(len[cur]+2); // 新建节点
        fail[now]=ch[get_fail(fail[cur])][c];
        //和AC自动机一样建立fail指针，以便失配后跳转
        hf[now] = ch[get_fail(hf[cur])][c];
        while(len[hf[now]] << 1 > len[now]) hf[now] = fail[hf[now]];
        ch[cur][c]=now;
        ph[now] = 1 + ph[hf[now]] * ((len[now] >> 1) == len[hf[now]]);
    }
    last=ch[cur][c];
    tot[last]++;
}
ll ans()
{
	ll ans = 0;
	for(int i = p - 1; ~i; -- i)
		tot[fail[i]] += tot[i], ans += (ll)(tot[i] * ph[i]);
	//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
	return ans;
}
int main()
{
	int T;
	scanf("%d", &T);
	while(T --)
	{
	    scanf("%s",s);
	    int n = strlen(s);
	    init();
	    for(int i = 0; i < n; ++ i)
	    	add(s[i] - 'a' + 1, i);
	    printf("%lld\n", ans());
	}
	return 0;
}

2018年 南京网络赛 Problem I Skr

求一个数字串中所有本质不同的回文子串之和。

疯狂改板子。。不过还差几分钟就能交了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
# include <bits/stdc++.h>
#define lowbit(x) (x)&(-x) 
#define Abs(x) ((x) > 0 ? (x) : (-(x))) 
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++) 
#define FORP(i,a,b) for(int i=(a);i<=(b);i++) 
#define FORM(i,a,b) for(int i=(a);i>=(b);i--) 
#define ls(a,b) (((a)+(b)) << 1) 
#define rs(a,b) (((a)+(b)) >> 1) 
#define getlc(a) ch[(a)][0] 
#define getrc(a) ch[(a)][1] 
   
#define maxn 2000005
#define maxc 10
#define maxm 2000005
#define INF 1070000000 
using namespace std; 
typedef long long ll; 
typedef unsigned long long ull; 
   
template<class T> inline 
void read(T& num){ 
    num = 0; bool f = true;char ch = getchar(); 
    while(ch < '0' || ch > '9') { if(ch == '-') f = false;ch = getchar();} 
    while(ch >= '0' && ch <= '9') {num = num * 10 + ch - '0';ch = getchar();} 
    num = f ? num: -num; 
}
int outs[100];
template<class T> inline
void write(T x){
    if (x==0) {putchar('0'); putchar('\n'); return;}
    if (x<0) {putchar('-'); x=-x;}
    int num=0;
    while (x){ outs[num++]=(x%10); x=x/10;}
    FORM(i,num-1,0) putchar(outs[i]+'0'); putchar('\n');
}
/*==================split line==================*/
int tot[maxn],num[maxn],len[maxn],fail[maxn],S[maxn],ch[maxn][maxc];
char s[maxn];
int p,last,cnt;
long long ans;
const long long mod = 1e9 + 7;
int newnode(int l){
    tot[p]=0; num[p]=0; len[p]=l;
    return p++;
}
void init(){
    p=0; memset(ch,0,sizeof(ch));
    newnode(0); newnode(-1);
    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
}
int get_fail(int x){
    while(S[cnt-len[x]-1]!=S[cnt]) x=fail[x];
    return x;
}
void add(int c,int pos){
    S[++cnt]=c;
    int cur=get_fail(last);
    if (!ch[cur][c]){
        int now=newnode(len[cur]+2);
        fail[now]=ch[get_fail(fail[cur])][c];
        ch[cur][c]=now; //ans++;
    }
    last=ch[cur][c];
    tot[last]++;
}
ll ten[maxn];
void bianli(int cur, long long p, int len)
{
	if(cur == 0) //偶数的情况
	{
		for(int i = 0; i < 10; i ++)
			if(ch[cur][i])
			{
				ans = (ans + i * 10 % mod + i) % mod;
				bianli(ch[cur][i], i * 10 % mod + i, 2);
			}
		return ;
	}
	if(cur == 1)
	{
		for(int i = 0; i < 10; i ++)
			if(ch[cur][i])
			{
				ans = (ans + i) % mod;
				bianli(ch[cur][i], i, 1);
			}
		return ;
	}
	for(int i = 0; i < 10; i ++)
		if(ch[cur][i])
		{
			ans = (ans + (1ll * i * ten[len + 1] % mod + p * 10 % mod + i) % mod) % mod;
			bianli(ch[cur][i], (1ll * i * ten[len + 1] % mod + p * 10 % mod + i) % mod, len + 2);
		}
}
int main(){
    ans = 0;
    scanf("%s",s);
    int n = strlen(s);
    init();
    //FORP(i,0,n-1) add(s[i]-'0'+1,i);
    ten[0] = 1;
    for(int i = 1; i <= n + 1; i ++)
    	ten[i] = ten[i - 1] * 10 % mod;
    for(int i = 0; i < n; ++ i)
    	add(s[i] - '0', i);
    bianli(0, 0, 0); //xjb 写的，估计以后要改
    bianli(1, 0, 0);
    printf("%lld\n", ans);
}

HDU 5658 CA Loves Palindromic

问任意区间中本质不同的回文串数量。因为长度才1000就暴力枚举区间即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 1000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
char s[maxn];
	
struct PA
{
	int num[maxn],len[maxn],fail[maxn],S[maxn],ch[maxn][maxc];
	char s[maxn];
	int p,last,cnt;
	ll tot[maxn];
	
	//tot 表示当前节点表示回文串中的后缀子回文串的个数(包括自己)
	//len 当前节点表示的回文串的长度
	//S 存放添加的字符
	//p节点个数 cnt字符串长度
	
	int newnode(int l){
	    tot[p]=0; num[p]=0; len[p]=l;
	    return p++;
	}
	void init(){
	    p=0; memset(ch,0,sizeof(ch));
	    newnode(0); newnode(-1);
	    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
	    //开头放一个字符集中没有的字符，减少特判
	}
	int get_fail(int x){ //和KMP一样，失配后找一个尽量最长的
	    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
	    return x;
	}
	void add(int c,int pos){ //返回以当前字符结尾的回文串个数
	    S[++cnt]=c;
	    int cur=get_fail(last); //通过上一个回文串找这个回文串的匹配位置
	    if (!ch[cur][c]){
	    	//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
	        int now=newnode(len[cur]+2); // 新建节点
	        fail[now]=ch[get_fail(fail[cur])][c];
	        //和AC自动机一样建立fail指针，以便失配后跳转
	        ch[cur][c]=now;
	    }
	    last=ch[cur][c];
	    tot[last]++;
	}
	ll ans()
	{
		ll ans = 0;
		for(int i = p - 1; ~i; -- i)
			tot[fail[i]] += tot[i];
		//父亲累加儿子的cnt，因为如果fail[v]=u，则u一定是v的子回文串！
		return ans;
	}
};
	
PA pa;
	
int ans[maxn][maxn];
	
int main()
{
	int T, m, f, t;
	scanf("%d", &T);
	while(T --)
	{
		scanf("%s", s);
		int ssize = strlen(s);
		for(int i = 0; i < ssize; ++ i)
		{
			pa.init();
			for(int j = i; j < ssize; ++ j)
				pa.add(s[j], j - i), ans[i][j] = pa.p - 2; //因为初始有两个节点 
		}
		scanf("%d", &m);
		while(m --)
		{
			scanf("%d %d", &f, &t);
			-- f, -- t;
			printf("%d\n", ans[f][t]);
		}
	}
	return 0;
}

BZOJ 2565 最长双回文串

求最长的位置，这个位置满足：把一个串切成两个串，这两个串都是回文串。

倒着顺着跑两遍 PA 就行了。。。

为什么倒着的时候，要全部遍历，正着的时候就不用遍历头了？

因为要对应位置，见下一题的分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 100000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
int n;
char s[maxn];
struct PA
{
	int num[maxn],len[maxn],fail[maxn],S[maxn], ch[maxn][maxc];	
	int p,last,cnt, ans[maxn];
	ll tot[maxn];
	
	//tot 表示当前节点表示回文串中的后缀子回文串的个数(包括自己)
	//len 当前节点表示的回文串的长度
	//S 存放添加的字符
	//p节点个数 cnt字符串长度
	
	int newnode(int l){
	    tot[p]=0; num[p]=0; len[p]=l;
	    return p++;
	}
	void init(){
	    p=0; memset(ch,0,sizeof(ch));
	    newnode(0); newnode(-1);
	    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
	    //开头放一个字符集中没有的字符，减少特判
	}
	int get_fail(int x){ //和KMP一样，失配后找一个尽量最长的
	    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
	    return x;
	}
	void add(int c,int pos){ //返回以当前字符结尾的回文串个数
	    S[++cnt]=c;
	    int cur=get_fail(last); //通过上一个回文串找这个回文串的匹配位置
	    if (!ch[cur][c]){
	    	//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
	        int now=newnode(len[cur]+2); // 新建节点
	        fail[now]=ch[get_fail(fail[cur])][c];
	        //和AC自动机一样建立fail指针，以便失配后跳转
	        ch[cur][c]=now;
	    }
	    last = ch[cur][c];
	    tot[last]++;
	    ans[pos] = len[last];
	}
};
	
PA shunx, nix;
	
ll cnt_s[maxn], cnt_n[maxn];
	
int main()
{
    scanf("%s", s);
    n = strlen(s);
    shunx.init();
    nix.init();
    for(int i = 0; i < n; ++ i)
    	shunx.add(s[i] - 'a' + 1, i), cnt_s[i] = shunx.ans[i];
    reverse(s, s + n);
    //cout << s << endl;
    for(int i = 0; i < n; ++ i)
    	nix.add(s[i] - 'a' + 1, i), cnt_n[i] = nix.ans[i];
    //for(int i = 1; i <= n; ++ i)	
    //	cout << cnt_s[i - 2] << ' ' << cnt_n[n - i] << endl;
    ll ans = 0;
    for(int i = 2; i <= n; ++ i)
    	ans = max(ans, cnt_s[i - 2] + cnt_n[n - i]);
    printf("%lld\n", ans);
	return 0;
}

HDU 5157 Harry and magic string

求每个点的前面和后面的本质回文字符串的数量和。

上一道题就没搞清楚位置怎么算，这道题就出事了。。

按照样例2来说：

字符位置 0 1 2 3
字符 a a a a
x[i] = 正向建回文树的num[i] 1 2 3 4
y[i] = 逆向建回文树的num[i] 4 3 2 1
sy[i] = y[i] 的后缀和 10 6 3 1

如果你要算第 0 个字符的数量和的话，从表中可以看出，我们需要计算 x[0] * sy[1] 。这是因为 sy[0] 表示的是从 4 到 0 ，就与 x[0] 重复了。

总结成一句话，对于每个点就是 x[i] * sy[i + 1]。

上一道题与这道题的位置分析是一个道理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
//#define NOSTDCPP
//#define Cpp11
//#define Linux_System
#ifndef NOSTDCPP
	
#include <bits/stdc++.h>
	
#else
	
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <complex>
#include <cstring>
#include <cstdio>
#include <deque>
#include <exception>
#include <functional>
#include <iomanip>
#include <iostream>
#include <istream>
#include <iterator>
#include <list>
#include <map>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
	
#endif
	
# ifdef Linux_System
# define getchar getchar_unlocked
# define putchar putchar_unlocked
# endif
	
# define RESET(_) memset(_, 0, sizeof(_))
# define RESET_(_, val) memset(_, val, sizeof(_))
# define fi first
# define se second
# define pb push_back
# define midf(x, y) ((x + y) >> 1)
# define DXA(_) ((_ << 1))
# define DXB(_) ((_ << 1) | 1)
	
# define next __Chtholly__
# define x1 __Mercury__
# define y1 __bbtl04__
# define index __ikooo__
	
using namespace std;
	
typedef long long ll;
typedef vector <int> vi;
typedef set <int> si;
typedef pair <int, int> pii;
typedef long double ld;
	
const int MOD = 1e9 + 7;
const int maxn = 100000 + 10;
const int maxc = 30;
const double pi = acos(-1.0);
const double eps = 1e-6;
	
ll myrand(ll mod){return ((ll)rand() << 32 ^ (ll)rand() << 16 ^ rand()) % mod;}
	
template <class T>
inline bool scan_d(T & ret)
{
	char c;
	int sgn;
	if(c = getchar(), c == EOF)return false;
	while(c != '-' && (c < '0' || c > '9'))c = getchar();
	sgn = (c == '-') ? -1 : 1;
	ret = (c == '-') ? 0 : (c - '0');
	while(c = getchar(), c >= '0' && c <= '9')
		ret = ret * 10 + (c - '0');
	ret *= sgn;
	return true;
}
#ifdef Cpp11
template <class T, class ... Args>
inline bool scan_d(T & ret, Args & ... args)
{
	scan_d(ret);
	scan_d(args...);
}
#define cin.tie(0); cin.tie(nullptr);
#define cout.tie(0); cout.tie(nullptr);
#endif
inline bool scan_ch(char &ch)
{
	if(ch = getchar(), ch == EOF)return false;
	while(ch == ' ' || ch == '\n')ch = getchar();
	return true;
}
	
inline void out_number(ll x)
{
	if(x < 0)
	{
		putchar('-');
		out_number(- x);
		return ;
	}
	if(x > 9)out_number(x / 10);
	putchar(x % 10 + '0');
}
	
int n;
char s[maxn];
struct PA
{
	int num[maxn],len[maxn],fail[maxn],S[maxn], ch[maxn][maxc];	
	int p,last,cnt, ans[maxn];
	ll tot[maxn];
	
	//tot 表示当前节点表示回文串中的后缀子回文串的个数(包括自己)
	//len 当前节点表示的回文串的长度
	//S 存放添加的字符
	//p节点个数 cnt字符串长度
	
	int newnode(int l){
	    tot[p]=0; num[p]=0; len[p]=l;
	    return p++;
	}
	void init(){
	    p=0; memset(ch,0,sizeof(ch));
	    newnode(0); newnode(-1);
	    last=0; cnt=0; S[cnt]=-1; fail[0]=1;
	    //开头放一个字符集中没有的字符，减少特判
	}
	int get_fail(int x){ //和KMP一样，失配后找一个尽量最长的
	    while(S[cnt-len[x]-1]!=S[cnt]) x = fail[x];
	    return x;
	}
	ll add(int c,int pos){ //返回以当前字符结尾的回文串个数
	    S[++cnt]=c;
	    int cur=get_fail(last); //通过上一个回文串找这个回文串的匹配位置
	    if (!ch[cur][c]){
	    	//如果这个回文串没有出现过，说明出现了一个新的本质不同的回文串
	        int now=newnode(len[cur]+2); // 新建节点
	        fail[now]=ch[get_fail(fail[cur])][c];
	        //和AC自动机一样建立fail指针，以便失配后跳转
	        ch[cur][c]=now;
	        num[now] = num[fail[now]] + 1;
	        //tot[now] = tot[fail[now]] + 1;
	    }
	    last = ch[cur][c];
	    tot[last]++;
	    return ans[pos] = num[last];
	}
};
	
PA shunx;
	
ll cnt_s[maxn], cnt_n[maxn];
	
int main()
{
    while(~ scanf("%s", s))
    {
	    n = strlen(s);
	    shunx.init();
	    //nix.init();
	    for(int i = 0; i < n; ++ i)
	    	cnt_s[i] = shunx.add(s[i] - 'a' + 1, i);
	    reverse(s, s + n);
	    //cout << s << endl;
	    shunx.init();
	    cnt_n[n] = 0;
	    for(int i = 0; i < n; ++ i)
	    	cnt_n[n - i - 1] = shunx.add(s[i] - 'a' + 1, i) + cnt_n[n - i];
	    /*
	    for(int i = 0; i < n; ++ i)	
	    	cout << cnt_s[i] << ' ' << cnt_n[i + 1] << endl;
	    */	
	    ll ans = 0;
	    for(int i = 0; i < n; ++ i)
	    	ans += cnt_s[i] * cnt_n[i + 1];
	    printf("%lld\n", ans);
	}
	return 0;
}

本文标题:回文树

文章作者:Babydragon

发布时间:2018-09-02, 01:20:00

最后更新:2018-09-07, 20:52:55

原始链接:http://baolintian.github.io/2018/09/02/回文树/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 回文树
    1. 1.1. 概述
    2. 1.2. 回文树可以解决的问题
    3. 1.3. 回文树的结构
    4. 1.4. 回文树模板
    5. 1.5. 回文树的应用
      1. 1.5.1. UOJ 103 Palindromes
      2. 1.5.2. HDU 3948 The Number of Palindromes
      3. 1.5.3. CodeChef PALPROB Palindromeness
      4. 1.5.4. 2018年 南京网络赛 Problem I Skr
      5. 1.5.5. HDU 5658 CA Loves Palindromic
      6. 1.5.6. BZOJ 2565 最长双回文串
      7. 1.5.7. HDU 5157 Harry and magic string
{{ live2d() }}