对于回文树在线前后加入删除算法的更详细阐述和改进

b6e0_ · 2024-08-05 20:56:54 · 算法·理论

感谢 Glacy 对于结论证明的贡献。

个人感觉论文里写的不太清楚，所以自己写一篇补充说明，包含自己解决这个问题的思想历程，以及对算法的一些细节上的改进。

插入没问题，跑非均摊的插入算法即可；删除有两个困难：求出当前串的最长回文前缀/后缀；判断回文树上的这个节点是否需要删除。下面挨个解决。

对于困难一，我们记 l_i 为当前串从 i 开始的后缀的最长回文前缀，r_i 为以 i 结尾的前缀的最长回文后缀，由于插入/删除单个字符时，会对非常多的 l_i,r_i 造成修改，而我们要保持 O(1) 的复杂度，无法实时维护所有 l_i,r_i 的正确值。但是，考虑到我们需要一个 l_i 的值时，i 左边的字符一定都被删光了，r_i 同理，所以考虑延迟维护。

例如，假设当前的字符串是 s_2s_3\cdots s_n，在字符串开头插入 s_1。设 s_{1\sim n} 的回文前缀从短到长分别为 [1,p_1],[1,p_2],\cdots,[1,p_m]。插入 s_1 会使得对于每个 i(1\le i\le m)，r_{p_i}=[1,p_i]，但是我们考虑只修改 r_{p_m} 的值，在删除 s_{p_m} 时再找到 p_{m-1} 并修改 r_{p_{m-1}}，大概就是这种思想。但是并不能直接这么干，因为假如之后又在开头插入了一些字符使得实际上的 r_{p_{m-1}} 不再是 [1,p_{m-1}]，此时删除 s_{p_m}，我们无法得知此时是否要修改 s_{p_m} 为 [1,p_{m-1}]。

有人可能会说，比较一下 s_{p_{m-1}} 当前存储的字符串和 [1,p_{m-1}] 的长度就行了。但是删除时也会产生问题：如果从 1\sim n 挨个（在字符串末尾）插入 s_i，此时所有 r_i 维护的都是正确的值；然后删除 s_1，这会导致 r_{p_1},r_{p_2},\cdots,r_{p_m} 存储的都变成一个当前字符串中不存在的东西，这会导致刚才比较字符串长度的想法失效。

继续修补以上的算法看上去没有前途：太混乱了。考虑我们实际需要的，其实是维护一些信息，满足插入删除时只会有 O(1) 的变化，并且这些信息能推导出当前字符串的最长回文前后缀。经过一些尝试，可以给出如下定义：

定义 s 的子串 s[l..r] 是重要的，当且仅当它是回文的，且不存在 l'<l 满足 s[l'..r] 是回文的，且不存在 r'>r 满足 s[l..r'] 是回文的。注意“重要”与“极长”的区别。

注意到重要子串的性质：s 的所有前缀中，重要子串有且仅有一个，其就是 s 的最长回文前缀；后缀同理。于是，我们考虑维护所有重要子串，令 l_i 和 r_i 分别存储以 i 开头/结尾的重要子串（根据定义，若存在则唯一；不存在则设为 0），这样就能解决我们的问题。

设当前 s 的最长回文后缀为 [l,n]，它的最长回文真前缀/后缀的长度为 x。

在末尾插入 s_n 时，我们加入了一个重要子串 [l,n]，并且将 [l,l+x-1] 变为不重要。开头插入同理。

在末尾删除 s_n 时，[l,n] 变为不重要，并且 [l,l+x-1] 可能从不重要变为重要，依据 r_{l+x-1} 当前的值即可判断出 [l,l+x-1] 是否变为重要。开头删除同理。

于是插入删除时造成的修改都是 O(1) 的，我们解决了困难一。

对于困难二，我们考虑类似只有一侧插入删除时的方法，对于回文树上每个节点，记录它成为了多少次前缀的最长回文后缀，或后缀的最长回文前缀，记为 \text{tg}。下面我们证明，对于得到的字符串 s，无论采用何种顺序插入，得到的 \text{tg} 值都是一样的。

我们只需要证明，对于任意字符串 s，将其中的字符正着插入一遍和倒着插入一遍，得到的 \text{tg} 值一样即可。如果该命题成立，则运用归纳法，设长度 <k 的两个插入序列得到的 \text{tg} 值相同，若第 k 次插入在同侧，则显然成立；若在异侧，则根据归纳假设，可以将两个操作序列等价地看做是正着插入和倒着插入的，此时得到的 \text{tg} 相同。

该命题等价于，s 的所有前缀的最长回文后缀组成的可重集（记为 T），和 s 反串的这个集合相等。记 s 的所有回文子串的字符串本身组成的可重集为 S，我们尝试证明 S 唯一决定了 T。考虑字符串长度从大到小地枚举 S 中的元素，设当前枚举到 t，我们在 S 中删去 t 的所有回文真后缀恰好一个。整个过程结束后 S=T，于是原命题得证。

这样，我们说明了 \text{tg} 值是良定义的，并且执行插入删除时直接用单侧插入删除的方法维护 \text{tg} 值是正确的。于是困难二被解决。

相比于论文中的算法，本算法无需使用哈希表维护 \text{cnt} 数组，并且将 \text{imp} 和 \text{child} 两个数组缩减为了一个 \text{tg} 数组，更为简洁。

其实，我对论文中的算法是有疑问的，如果从左到右依次在末尾插入 \tt{abacaba} 后删除开头的字符，是不是会出现 \text{cnt}_{5,7}（即字符串 \tt{aba} 靠后的一次出现） 变为 -1 的情况？求助，如有人能在评论区解答我将感激不尽。

本算法的代码实现（经过了对拍验证），其中 o=1,2,3,4 分别表示开头插入，末尾插入，开头删除，末尾删除：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1000005;
int a[MN*2],L=MN,R=MN-1,cnt=2,len[MN],fail[MN],tr[MN][26],fa[MN],tg[MN],qk[MN][26],lm[MN*2],rm[MN*2];
int main()
{
    int q;
    cin>>q;
    memset(a,-1,sizeof a);
    len[1]=-1,fail[1]=fail[2]=1;
    for(int i=0;i<26;i++)
        qk[1][i]=qk[2][i]=1;
    for(int Q=1;Q<=q;Q++)
    {
        int o,c,xl,xr;
        cin>>o;
        if(L>R)
            xl=xr=1;
        else
            xl=lm[L],xr=rm[R];
        if(o==1)
        {
            cin>>c;
            a[--L]=c;
            if(a[L+len[xl]+1]!=c)
                xl=qk[xl][c];
            if(tr[xl][c])
                xl=tr[xl][c];
            else
            {
                tr[xl][c]=++cnt;
                fa[cnt]=xl;
                len[cnt]=len[xl]+2;
                if(len[cnt]==1)
                    fail[cnt]=2;
                else
                    fail[cnt]=tr[qk[xl][c]][c];
                xl=cnt;
                for(int i=0;i<26;i++)
                    qk[xl][i]=qk[fail[xl]][i];
                qk[xl][a[L+len[fail[xl]]]]=fail[xl];
            }
            int r=L+len[xl]-1,t=fail[xl],l=r-len[t]+1;
            lm[L]=rm[r]=xl;
            if(len[xl]>1&&lm[l]==t)
                lm[l]=0;
            tg[xl]++;
        }
        else if(o==2)
        {
            cin>>c;
            a[++R]=c;
            if(a[R-len[xr]-1]!=c)
                xr=qk[xr][c];
            if(tr[xr][c])
                xr=tr[xr][c];
            else
            {
                tr[xr][c]=++cnt;
                fa[cnt]=xr;
                len[cnt]=len[xr]+2;
                if(len[cnt]==1)
                    fail[cnt]=2;
                else
                    fail[cnt]=tr[qk[xr][c]][c];
                xr=cnt;
                for(int i=0;i<26;i++)
                    qk[xr][i]=qk[fail[xr]][i];
                qk[xr][a[R-len[fail[xr]]]]=fail[xr];
            }
            int l=R-len[xr]+1,t=fail[xr],r=l+len[t]-1;
            rm[R]=lm[l]=xr;
            if(len[xr]>1&&rm[r]==t)
                rm[r]=0;
            tg[xr]++;
        }
        else if(o==3)
        {
            int r=L+len[xl]-1,t=fail[xl],l=r-len[t]+1;
            if(len[xl]>1&&len[lm[l]]<=len[t])
                lm[l]=rm[r]=t;
            else
                rm[r]=0;
            lm[L]=rm[L]=0;
            if(!(--tg[xl]))
                tr[fa[xl]][a[L]]=0;
            a[L++]=-1;
        }
        else
        {
            int l=R-len[xr]+1,t=fail[xr],r=l+len[t]-1;
            if(len[xr]>1&&len[rm[r]]<=len[t])
                lm[l]=rm[r]=t;
            else
                lm[l]=0;
            rm[R]=lm[R]=0;
            if(!(--tg[xr]))
                tr[fa[xr]][a[R]]=0;
            a[R--]=-1;
        }
    }
    return 0;
}