回文树学习笔记

回文树学习笔记

神奇的数据结构 Palindromic Tree 回文树

功能简介

  1. 求一个串$S$中$[0,i]$中本质不同回文串的个数
  2. 求串$S$中每一个本质不同回文串出现的次数
  3. 求指定下标$i$结尾的回文串的个数

变量简介

  1. $len[i]$表示编号为$i$节点所表示的回文串的$len$。
  2. $next[i][c]$表示编号为$i$的节点表示的回文串在两边添加字符$c$之后会变成的回文串的编号。
  3. $fail[i]$表示节点$i$失配以后跳转后不等于自己的节点$i$所表示的回稳产的最长长度。
  4. $cnt[i]$表示节点$i$表示的本质不同的串的个数。
  5. $num[i]$表示以节点$i$表示的最长回文串的最右端点为回文串结尾的回文串个数。
  6. $last$指向新添加一个字母后所形成的最长回文串表示的节点。
  7. $S[i]$表示第$i$次添加的字符(初始化S[0]=不存在的字符)。
  8. $p$表示添加的节点个数。
  9. $n$表示添加的字符个数。

模板(抄的)

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
const int maxn = 1e5+10;
const int N = 26; // attention 用模板的时候要改变

struct Ptree{
int next[maxn][N];
int fail[maxn];
int cnt[maxn];
int num[maxn];
int len[maxn];
int S[maxn];
int last,n,p;
int newNode(int x){
rep(i,0,N) next[p][i] = 0;
cnt[p] = 0;num[p] = 0;len[p] = x;
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){
while(S[n-len[x]-1] != S[n]) x = fail[x];
return x;
}
void add(int c){
c -= 'a'; // attention 用模板的时候要改变
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];
next[cur][c] = now;
num[now] = num[fail[now]] + 1;
}
last = next[cur][c];
cnt[last]++;
}
void count(){
per(i,0,p) cnt[fail[i]] += cnt[i];
}
}

https://blog.csdn.net/u013368721/article/details/42100363