欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回文树(回文自动机)学习总结

程序员文章站 2022-06-10 22:17:39
...

Palindromic Tree,译名为“回文树”,是一种专门处理回文串的数据结构,类似于Manachar算法,但更为强大。是由两颗分别存储偶数回文串树和存储奇数回文串树组成,每个节点代表母串的回文串,两树之间中用fail指针连接。(摘自百度百科)

回文树可以很方便地解决大多数回文串相关的问题,例如以某一位开始的最长回文串,次长回文串…,某个回文串在整个文本中出现的次数,最长回文串是谁…功能十分强大,而且代码简洁,效率高(nlogn),可谓是不可多得的回文串神器.下面则是我对回文树的一些粗糙的理解.

学习回文树需要字典树的知识,不过字典树大家应该都会吧,就不赘述了…

我们都知道回文串有两种–长度为奇数的和长度为偶数的.所以我们的回文树有两个根结点分别为0号结点和1号节点,其中,0号结点为偶数回文串的根结点,1号结点为长度为奇数的回文串的根结点

回文树(回文自动机)学习总结
上图为回文树每个节点所代表的含义,下面就是回文树最核心的一个关系–fail数组的含义,先上图;

回文树(回文自动机)学习总结

(图片失真的好严重)

通过图片可以十分明显的观察出----fai指针指向的是以当前结点结尾的次长回文串
看出这点之后回文树的构造逻辑和代码就变得十分简单了…
上代码:

#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 10010
using namespace std;

struct node {
    int len[MAX];//每个节点所对应字符串的长度
    int fail[MAX];//******核心中的核心
    int nxt[MAX][200];//字典树
    int p, tot,last;//p为回文树中总节点个数,tot为插入的总字符个数
    int s[MAX];//已经插入的字符串
    void init()//构建两个空节点
    {
        p = 0;
        tot = 0;
        last = 0;
        newnode(0);
        newnode(-1);//-1精髓了(作用1:保证了奇回文串的长度为奇,作用2:保证getfail不会死循环)
        fail[0] = 1;//神来之笔
        s[0] = -1;//-1的意思为确保没有一个字符与第0位相等
    }

    int newnode(int l)
    {
        len[p] = l;
        return p++;
    }

    void insert(char c)
    {
        s[++tot] = c;
        int cur =getfail(last);//cur为当前要回文树中插入的节点的父节点
        if (!nxt[cur][c])
        {
            int now = newnode(len[cur] + 2);//新建结点
            fail[now] = nxt[getfail(fail[cur])][c];//找到以该节点结尾的次长回文串
            nxt[cur][c] = now;
        }
        last = nxt[cur][c];
    }

    int getfail(int x)//整个算法的核心
    {
        while (s[tot - len[x] - 1] != s[tot]) x = fail[x];
        return x;
    }

}pt;

int main()
{
    pt.init();
    char a[MAX];
    cin.getline(a,MAX);
    for (int i = 0; i < strlen(a); i++)
    {
        pt.insert(a[i]);
    }
    int ans = 0;
    for (int i = 2; i < pt.p; i++)
    {
        ans = max(ans,pt.len[i]);
    }
    cout << ans;
    return 0;
}

有没有被惊艳到?这么强大的算法竟然这么简洁. %大佬.
其实回文树的构造逻辑可以称的上是白痴了----若字符串中l到r之间的子串为回文串那么如果该字符串中第(l-1)位所对应的字符和(r+1)位所对应的字符一致,那么原字符串中(l-1)到(r+1)所对应的子串也是回文串, 但是如果第(l-1)位所对应的字符和(r+1)位所对应的字符不一致呢? 那就找以r为回文串结尾的次长回文串再进行上述判断就行了,什么?你问如果一直找不到?那是不存在的,仔细研究上面的代码就会发现,如果一直在x=fail[x]上迭代的话最终一定会回到1号节点(fail[0]立功!)而len[1]=-1;s[tot - len[x] - 1] 一定等于 s[tot] (妙啊).

如果上面的看懂了,回文树就会构建了,那么就可以解决很多回文串的问题了.
但是回文树的应用还没有就此结束,这个以后再更新吧.