非常简洁的回文树教程

定义

偶根$0$:长度为0的回文串所在节点

奇根$1$:长度为-1的回文串所在节点(为了便于处理)

$len[u]$:当前节点$u$维护的回文长度

$trans[u][c]$:转移函数,注意其中所有状态均为回文(单次转移相当于$u$节点代表字符串左右两边加上$c$)

$fail[u]$:失配指针,指向$u$最大匹配后缀回文的所在节点

前置理论

一个长度为$n$的字符串中,本质不同的回文子串个数也不超过$n$

对于在一个串中新增一个字符的情况下,本质不同回文子串个数最多新增1个

证明:

考虑增量过程中新增的字符$str[i]$,新增的回文肯定跟它有关(也就是肯定是$str[j...i]$的形式,$j$任取)

我们假设真的存在新增多个本质不同回文子串,从中挑出最长的一个串$s$

可以发现其它的回文子串即使存在也是以$s$的后缀形式存在

但作为回文,后缀出现过的,那么前缀也肯定出现过,因此是属于本质相同的子串,END

(不信就用$aaaaaaa$来感受下)

因此我们可以用$O(n)$个状态转移来表示所有本质不同的回文子串

构造过程

  1. 偶根的失配指针指向奇根,奇根必然不会失配(单个字符也能形成回文串)
  2. 采用增量的方法一个一个添加字符,假设现在添加字符$c$
  3. 维护$str[1...i)$后缀的最长回文字串$str[j...i)$,$j$任取,设所在节点为$u$
  4. 通过不断地寻找$u$的suffix-link($fail[..fail[u]]$),相当于缩短后缀,找到一个回文串$X$,使得满足在原串中符合$cXc$形式的回文串,设节点为$v$
  5. 如果存在,那我们不必理会,因为由状态存在得知是本质相同的(前面存在过的);否则新增$trans[u][c]$状态$t$,我们已知其长度就是$len[v]$多两个字符的长度(这个时候奇根直接+2就是巧妙的形成单个字符的回文串)
  6. 至于$fail[v]$,可以发现同样是同样是$u/w$的后缀加上$c$,直接继续在$w$的suffix-link上寻找符合$cYc$的状态即可,设为$w$,令$fail[v]=trans[w][c]$

好了已经构造完了,由于找$fail$的过程会使得$str[j...i]$中的$j$不断右移,因此总体来看,其成本还是$O(n)$

完成版

#include<bits/stdc++.h>
#define debug(xx) cout << "[line@" << __LINE__ << "] " << xx << endl
#define fast_io() do{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}while(0)
#define var auto
#define dect decltype
using namespace std;
using ll = int_fast64_t;
namespace util {
    template<typename T>
    inline void alloc(vector<T> &v) {
        v.emplace_back();
    }
    template<typename T>
    inline void empb(vector<T> &v,const T &arg) {
        v.emplace_back(arg);
    }
    template<typename T>
    inline void pb(vector<T> &v,const T &arg) {
        v.push_back(arg);
    }
}

using namespace util;
struct PT {
    vector<array<int,26>> trans;
    vector<int> fail;
    vector<int> len;
    int last;
    string str;

    int state(int f,int l) {
        empb(trans,{});
        empb(fail,f);
        empb(len,l);
        return len.size()-1;
    }

    PT(const string &s) {
        state(1,0); // even root
        state(-1,-1); // odd root
        last = 1;
        str = s;
        for(int i = 0; i < str.length(); add(i++));
    }

    int get_suffix(int idx,int v) {
        while(str[idx-len[v]-1] != str[idx]) v = fail[v];
        return v;
    }

    void add(int idx) {
        int c = str[idx] - 'a';
        int u = last;
        int v = get_suffix(idx,u);
        if(!trans[v][c]) {
            int w = get_suffix(idx,fail[v]);
            int t = state(trans[w][c],len[v]+2);
            trans[v][c] = t;
        }
        last = trans[v][c]; // last也是每个端点为结束所代表的最长回文后缀
    }

};

int main() {
    string s = "aabaaa";
    PT pt(s);
    int mx = 1;
    for(int i = 0; i < pt.len.size(); i++) {
        mx = max(mx,pt.len[i]);
    }
    cout << mx << endl; // O(n)求最长回文子串的长度
    return 0;
}

参考

http://adilet.org/blog/palindromic-tree/

发表评论

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