锐客网

  1. 首页 > it技术 > >

ACM|回文树（自动机）（练习和总结）

ACMProblems

回文树是一种强大的回文字符串处理算法，他的构造过程实际上和KMP多少有些相似，这里https://blog.csdn.net/u013368721/article/details/42100363，讲的很是仔细。
下面摘录几个例题。
URAL 1960 Palindromes and Super Abilities
每次加一个新节点，说明了有一个新的回文串产生。这个感觉真的很重要啊……我们在自动机里记录一下就好
URAL 2040 Palindromes and Super Abilities 2
和上面的题，让add函数，返回是不是产生了新的串，出题人卡输出也是经典
BZOJ 3676 回文串
长度乘以次数，次数首先要向父节点更新，为什么呢。首先子节点是父节点扩展来的，子节点扩展的相当于是从一个小的的回文串，添加了字符，变成了大的回文串。说明子串出现的得次数需要向父串传递（fail）
HYSBZ 2160 拉拉队排练
求出前k长的奇数长度回文子串，对他们的长度求乘积。
所有的意味着我们要把每个节点代表的唯一字符串的长度和出现的次数都处理出来，这道题有点卡常……
HDU 5658 CA Loves Palindromic
这道题数据范围很小，我们只要把每一个询问暴力都处理出来就行，我们让自动机的add函数返回当前添加过字符后，自动机位置上有的多少个回文串。
HDU 5157 Harry and magic string
求出不相交的回文串有多少对
首先，我们反着添加一下，让add返回当前位置的回文串个数num，顺便求一个后缀和，这样就相当于处理出了每个位置右边有多少个回文串，然后我们正着添加一下，这样左边的和右边的乘一下就是答案，求和就ok、
CodeForces 17E Palisection
处理回文串的前后缀和也是一类经典问题，这道题要我们求出相交的回文串的个数。
我们可以利用上面的办法，通过所有的回文串对数 - 不相交的对数来求最后的答案，卡内存……
【ACM|回文树（自动机）（练习和总结）】HYSBZ 2565 最长双回文串
把一个串劈开，左右两边是回文串的最长字串
可以想到枚举分割点，那么我们建两个自动机（应该是建两次，偷了个懒），一个是正向插入，一个是反向。这两个自动机都维护一个这个回文串能向左延伸的长度。反向的就是向右，然后枚举分割点判断下就ok
HDU 5421 Victor and String
维护一个可以两边都可以添加的回文自动机，那么我们首先要解决这么几个问题：
last指针的位置：我们开两个变量存，代表两边构造到了什么位置
fail的寻找，由于我们分成了左右，相当于是从中间向左向右找，这个时候就需要一个辅助变量tot来记录构造到的位置，方便我们进行寻找。
左右两边的影响：在一边添加实际上会影响到另一边的指针，我们利用上面的tot变量判断左右两边是不死连在一起。

#include #include #include #include #include #include #include #include #include #include #include #define pr pair #define fi first #define se second #define mp make_pair #define ll long long using namespace std; const int MAXN = 1e5+10 ; const int N = 26 ; struct Palindromic_Tree { int next[MAXN*2][N] ; //next指针，next指针和字典树类似，指向的串为当前串两端加上同一个字符构成 int fail[MAXN*2] ; //fail指针，失配后跳转到fail指针指向的节点 int len[MAXN*2] ; //len[i]表示节点i表示的回文串的长度 int S[MAXN*2] ; //存放添加的字符 int tot[2]; int num[MAXN*2]; int last[2] ; //指向上一个字符所在的节点，方便下一次add int n ; //字符数组指针 int p ; //节点指针int newnode ( int l) {//新建节点 for ( int i = 0 ; i < N ; ++ i ) next[p][i] = 0 ; len[p] = l ; num[p] = 0; return p ++ ; }void init () {//初始化 p = 0 ; newnode (0 ) ; newnode ( -1 ) ; last[0] = last[1] = 0 ; tot[0] = MAXN - 5; tot[1] = MAXN - 6; n = 0 ; //S[n] = -1 ; //开头放一个字符集中没有的字符，减少特判 fail[0] = 1 ; }int get_fail ( int x ,int k) {//和KMP一样，失配后找一个尽量最长的 S[tot[0]-1]=-1; S[tot[1]+1]=-1; while(S[tot[k]]!=S[tot[k]+(k?-1:1)*(len[x]+1)]) x=fail[x]; return x; }int add ( int x ,int k) { x-='a'; S[tot[k]+=(k?1:-1)]=x; int cur=get_fail(last[k],k); if(!(last[k]=next[cur][x])) { int now=newnode(len[cur]+2); fail[now]=next[get_fail(fail[cur],k)][x]; next[cur][x]=now; num[now]=num[fail[now]]+1; last[k]=now; if(len[last[k]]==tot[1]-tot[0]+1)last[k^1]=last[k]; } return num[last[k]]; } }pam ; char buf[MAXN]; char s[10]; int main() { int q; while(scanf("%d",&q) != EOF) { pam.init(); int op; ll ans = 0; for(int i = 0; i

    推荐阅读


    上一篇：购物车js页面

    下一篇：C语言|C语言 基础数字输出左直角三角形