Noble 的博客

Noble 的博客

♡虹蓝♡

题解 P5829 【【模板】失配树】

posted on 2019-12-19 10:38:51 | under 题解 |

几年不更新一次的博客

前排Orz出题人和扶苏爷。

完全没听说过border树这个东西。。。。。

但是我们可以发现,border的定义和我们做kmp时所求的fail数组基本一致。

一个显然的结论是,对于A<--fail--B<--fail--C,A与C显然能也形成border。

根据这个传递性,我们就可以在fail数组上倍增,二分最靠右的交汇点编号,让两个点倍增去跳即可,O(nlog^2n)。

回忆树上倍增lca,这里之所以要二分的原因就是没法把两个点提到同一高度(这里相当于以编号作为高度,因此每个点高度都不同)。

模仿树上倍增的套路,按照fail链长度给每个点设置一下高度,树上倍增即可。时间复杂度O(nlogn),即O(能过)。

要注意的是因为border不能是整个串,所以两个点必须都跳至少一次。

(不知道这个是不是border树)

不过本题并没必要显式的连边建一颗树出来。

#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int kmaxlog=25;
const int kmaxn=1000000+5;
const int ml=21;
int fail[kmaxn];
int fa[kmaxn][kmaxlog];
int dis[kmaxn];
char s[kmaxn];
int n,q;
void init()
{
    int p=0;
    for(int i=2;i<=n;++i)
    {
        while(p&&s[p+1]!=s[i])
            p=fail[p];
        if(s[p+1]==s[i])++p;
        fail[i]=p;
        dis[i]=dis[p]+1;
        fa[i][0]=p;
    }
    for(int k=1;k<=ml;++k)
    {
        for(int i=1;i<=n;++i)
            fa[i][k]=fa[fa[i][k-1]][k-1];
    }
}
int jmp(int x,int h)
{
    if(dis[x]<=h)return x;
    for(int i=ml;i>=0;--i)
    {
        if(dis[fa[x][i]]>h)
            x=fa[x][i];
    }
    return fa[x][0];
}
int lca(int x,int y)
{
    if(dis[x]<dis[y])swap(x,y);
    x=jmp(x,dis[y]);
    for(int i=ml;i>=0;--i)
    {
        if(fa[x][i]!=fa[y][i])
        {
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int a,b;
int main()
{
    scanf("%s%d",&s[1],&q);
    n=strlen(s+1);
    init();
    while(q--)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}

刚看到题时候傻了以为hash就能搞,还看错了题,日常丢人。