回文树(回文自动机)学习总结
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] (妙啊).
如果上面的看懂了,回文树就会构建了,那么就可以解决很多回文串的问题了.
但是回文树的应用还没有就此结束,这个以后再更新吧.
上一篇: swift 开源框架
下一篇: 到底应不应该发展办公室恋情?