回文树学习笔记
回文树学习笔记
神奇的数据结构 Palindromic Tree 回文树
功能简介
- 求一个串$S$中$[0,i]$中本质不同回文串的个数
- 求串$S$中每一个本质不同回文串出现的次数
- 求指定下标$i$结尾的回文串的个数
变量简介
- $len[i]$表示编号为$i$节点所表示的回文串的$len$。
- $next[i][c]$表示编号为$i$的节点表示的回文串在两边添加字符$c$之后会变成的回文串的编号。
- $fail[i]$表示节点$i$失配以后跳转后不等于自己的节点$i$所表示的回稳产的最长长度。
- $cnt[i]$表示节点$i$表示的本质不同的串的个数。
- $num[i]$表示以节点$i$表示的最长回文串的最右端点为回文串结尾的回文串个数。
- $last$指向新添加一个字母后所形成的最长回文串表示的节点。
- $S[i]$表示第$i$次添加的字符(初始化S[0]=不存在的字符)。
- $p$表示添加的节点个数。
- $n$表示添加的字符个数。
模板(抄的)
1 | const int maxn = 1e5+10; |