回文树

应用场景

1.求串S前缀font>0~i内本质不同回文串的个数(两个串长度不同或者长度相同且至少有一个字符不同便是本质不同)

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

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

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

参考资料:

Palindromic Tree——回文树【处理一类回文串问题的强力工具】

17年国家集训队论文《回文树及其应用》

定义变量

1.len 表示编号为i的节点表示的回文串的长度(一个节点表示一个回文串)

2.next 表示编号为i的节点表示的回文串在两边添加字符c以后变成的回文串的编号(和字典树类似)。

3.fail 表示节点i失配以后跳转不等于自身的节点i表示的回文串的最长后缀回文串(和AC自动机类似)。

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

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

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

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

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

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

由于代码风格不同

本文全部代码均由上文博客地址中的代码改写而成

缺点: 速度慢

例如: UESTC-1999

上边的为我的模板的提交结果 TLE
下边的为改为原博主的模板后的提交结果,1421ms飘过
时限1500ms

Status Length Submitted RemoteRunId
Time Limit Exceeded on test 59 3139 2018-09-03 01:39:57 432786
Status Time Memory Length Submitted RemoteRunId
Accepted 1421ms 1524kB 2827 2018-09-03 01:51:36 432792

预定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int MAXN = 1e5+10;
const int N = 26;
char s[MAXN];
struct node
{
int next[N]; // next指针,next指针和字典树类似,指向的串为
// 当前穿两端加上同一个字符构成
int fail; // fail指针,失配后跳转到fail指针指向的节点
int cnt; // 表示节点i的本质不同的串的个数
// 建树时求出的不是完全的,最后Count()函数跑一遍以后才是正确的
int num; // 表示以节点i表示的最长回文串的最右端点为回文串结尾的回文个数
int len; // 表示以当前节点表示的最长回文串长度(一个节点表示一个回文串)
int S; // 存放添加的字符
}pam[MAXN];
int last; // 指向新添加一个字母后所形成的最长回文串表示的节点
int n; // 表示添加的字符个数
int p; // 表示添加的节点个数

新建节点

1
2
3
4
5
6
7
8
9
int newnode(int x)
{
for(int i = 0;i < N;i++)
pam[p].next[i] = 0;
pam[p].cnt = 0;
pam[p].num = 0;
pam[p].len = x;
return p++;
}

初始化

1
2
3
4
5
6
7
8
9
10
void Init()
{
p = 0;
newnode(0);
newnode(-1);
last = 0;
n = 0;
pam[n].S = -1; // 开头存放一个字符集中没有的字符,减少特判
pam[0].fail = 1;
}

构造失配指针

1
2
3
4
5
6
int get_fail(int x)
{
while(pam[n-pam[x].len-1].S != pam[n].S)
x = pam[x].fail;
return x;
}

添加字母

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void Add(int c)
{
c -= 'a';
pam[++n].S = c;
int cur = get_fail(last); // 通过上一个回文串找这个回文串的匹配位置
if(!pam[cur].next[c]) // 如果这个回文串没有出现过,说明出现了
// 一个新的本子不同的回文串
{
int now = newnode(pam[cur].len+2); // 新建节点
pam[now].fail = pam[get_fail(pam[cur].fail)].next[c];
// 和AC自动机一样建立fil指针,以便失败后回跳
pam[cur].next[c] = now;
pam[now].num = pam[pam[now].fail].num+1;
}
last = pam[cur].next[c];
pam[last].cnt++;
}

Count函数

1
2
3
4
5
6
7
8
void Count()
{
for(int i = p-1;i >= 0;--i)
{
pam[pam[i].fail].cnt += pam[i].cnt;
// 父亲累加儿子才cnt,因为如果fail[v] = u , 则u一定是v的子回文串
}
}

主函数

1
2
3
4
5
6
7
8
9
10
11
int main()
{
scanf("%s",s); // 读入字符串
int len = strlen(s);
Init(); // 初始化
for(int i = 0;i < len;i++)
Add(s[i]);
Count(); // Count()函数跑一遍cnt的值以后才是正确的
printf("balabalabala~~~");
return 0;
}

原文模板

速度比我改写的要快
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
const int MAXN = 100005 ;
const int N = 26 ;
struct Palindromic_Tree {
int next[MAXN][N] ;//next指针,next指针和字典树类似,指向的串为当前串两端加上同一个字符构成
int fail[MAXN] ;//fail指针,失配后跳转到fail指针指向的节点
int cnt[MAXN] ;
int num[MAXN] ;
int len[MAXN] ;//len[i]表示节点i表示的回文串的长度
int S[MAXN] ;//存放添加的字符
int last ;//指向上一个字符所在的节点,方便下一次add
int n ;//字符数组指针
int p ;//节点指针

int newnode ( int l ) {//新建节点
for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ;
cnt[p] = 0 ;
num[p] = 0 ;
len[p] = l ;
return p ++ ;
}

void init () {//初始化
p = 0 ;
newnode ( 0 ) ;
newnode ( -1 ) ;
last = 0 ;
n = 0 ;
S[n] = -1 ;//开头放一个字符集中没有的字符,减少特判
fail[0] = 1 ;
}

int get_fail ( int x ) {//和KMP一样,失配后找一个尽量最长的
while ( S[n - len[x] - 1] != S[n] ) x = fail[x] ;
return x ;
}

void add ( int c ) {
c -= 'a' ;
S[++ n] = c ;
int cur = get_fail ( last ) ;//通过上一个回文串找这个回文串的匹配位置
if ( !next[cur][c] ) {//如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串
int now = newnode ( len[cur] + 2 ) ;//新建节点
fail[now] = next[get_fail ( fail[cur] )][c] ;//和AC自动机一样建立fail指针,以便失配后跳转
next[cur][c] = now ;
num[now] = num[fail[now]] + 1 ;
}
last = next[cur][c] ;
cnt[last] ++ ;
}

void count () {
for ( int i = p - 1 ; i >= 0 ; -- i ) cnt[fail[i]] += cnt[i] ;
//父亲累加儿子的cnt,因为如果fail[v]=u,则u一定是v的子回文串!
}
} ;

练手习题

BZOJ3676

RunID Problem Result Memory Time Submit_Time
2937794 3676 Accepted 38036 kb 1252 ms 2018-09-03 00:59:48

UESTC-1999

Status Time Memory Length Submitted RemoteRunId
Accepted 1421ms 1524kB 2827 2018-09-03 01:51:36 432792