回文树

模拟赛出现了一道回文树模板题,打开论文学习一下
%negiizhao
题意大概是这样的:
维护一个数据结构,要求能够资瓷:
1. 在字符串\(S\)前端添加字符\(c\)
2. 在字符串\(S\)末端添加字符\(c\)
3. 查询现在的字符串内有多少个回文串,有多少个本质不同的回文串

显然是一个要求双向添加字符的回文树
这里只介绍如何在支持末端添加的基础上支持前端添加
考虑我们在末端添加时做了什么
我们找到一个最长的回文后缀,因为我们一定是在这个后缀的某一个回文后缀添加一个字符产生了新的回文串
所以我们在前端添加的时候也需要维护一个最长回文前缀
同时我们也需要维护前缀的\(fail\)指针
因为\(fail\)树上的节点都代表回文串,将他们反过来还是一样的,所以前缀对应的\(fail\)和后缀对应的\(fail\)是一样的
还要注意特判一下前(后)端插入对于最长回文后(前)缀的影响

发表评论

电子邮件地址不会被公开。 必填项已用*标注