hdu 4763 Theme Section 题解

题意简述

请你在一个字符串 $S$ 中找到最大的 $k$ ，使得存在长度为 $k$ 的前缀，后缀和子串，三者没有一点交集，且字符串值相等。算法必须线性（数据水，网上会被卡成n^2的算法也过了）（这是全网为数不多几个严格线性的题解）

思路框架

建一颗 $fail$ 树。然后用树上操作解决问题。

具体思路

我们用 $KMP$ 中的 $fail$ 数组建一颗树，从 $i$ 到 $fail_i$ 连一条边。不难发现， $0$ 就是根节点。

然后，我们先解决问题的几个部分解决。

前缀=后缀

前缀等于后缀并且位置不相等（即：长度不是n）。那满足条件的长度一定在 $n$ 号节点（不含）到根节点（含）的路径上。我们知道， $S$ 中满足前缀=后缀的长度就是fail[n]，fail[fail[n]]…0。也就是从 $n$ 到根的路径了。

前缀=某个子串

然后我们要找到一个子串和它们相等。（ $S$ 的）子串，就是（某个）前缀的（某个）后缀。而（某个）前缀的（某个）前缀还是（ $S$ 的）前缀。

所以，如果 $S$ 的一个以 $i$ 结尾的子串和 $S$ 的某个前缀相等，这个长度一定在 $i$ 到根的路径上。

合并

那么我们发现三者相等。所以，这个要求的长度，即在 $i$ 到根的路径上，也在 $n$ 到根的路径上。那么它就在 $i$ 和 $n$ 的 $LCA$ 到根的路径上。

稍微一想，长度最长，就是 $LCA$ 最深。我们要求 $LCA$ 最深，有这样一个方法：给每个点一个点权，初始为 $0$ 。然后从 $n$ 到 $1$ 的路径上都加上 $1$ 。对于每个 $i$ ，我们询问 $i$ 到根路径上点权的和，就是 $i$ 和 $n$ 的 $LCA$ 的深度。然后我们只需要维护一个树上前缀和，然后找到前缀和最大的位置即珂。

别忘了三者不能有相交

那咋整嘛。首先，前缀，后缀还有子串不能相交，那么长度就小于等于n的三分之一。由于我们我们在用上面的方法给点权+1的时候，判一下这个点的编号是否小于n的三分之一，如果满足，那才+1。

然后我们找到 $LCA$ 之后，不断判断 $LCA$ 的长度是否小于 $n$ 的三分之一，如果小于就跳 $fail$ 。当然，我们在找 $LCA$ 的时候，由于只有一组数据，我们也是一样的找法。用代码写，就是：

1	while(LCA上点权为0) 跳fail;

然后 $LCA$ 就是我们要求的最长长度了。记得要判一下无解。

时间复杂度

我们发现，我们刚刚说到了这样几个操作：

求字符串的fail
树上一条链加值
树上求前缀和

这些都是 $O(n)$ 完成的操作。所以我们的算法是严格 $O(n)$ 的，连 $log$ 都不带。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1666666
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)

    char s[N];int n;
    void Input()
    {
        scanf("%s",s+1);n=strlen(s+1);
    }

    int fail[N];
    void GetFail()
    {
        fail[1]=0;
        F(i,2,n)
        {
            int j=fail[i-1];
            while(s[j+1]!=s[i] and j) j=fail[j];
            if (s[j+1]==s[i]) ++j;
            fail[i]=j;
        }
    }
    int val[N],rsum[N];//点权，点权的前缀和
    void Soviet()
    {
        F(i,0,n+5) fail[i]=val[i]=rsum[i]=0;
        GetFail();//fail[i]是树上i节点的父亲
        int pos=n;
        while(pos) {{if (pos*3<=n) val[pos]=1;}pos=fail[pos];} //求出点权
        F(i,1,n) rsum[i]=rsum[fail[i]]+val[i];//维护前缀和

        int Max=0;
        F(i,2,n-1)//注意是2到n-1。当然你也珂以认为是n*1/3到n*2/3
        {
            if (!val[i]) if (rsum[i]>rsum[Max]) Max=i; //求出最深的LCA
        }

        if (rsum[Max]==0) {puts("0");return;}//判无解
        int LCA=Max;
        while(!val[LCA]) LCA=fail[LCA];//这里会死循环吗？
        printf("%d\n",LCA);
    }

    #define Flan void
    Flan IsMyWife()
    {
        int t;cin>>t;
        while(t--)
        {
            Input();
            Soviet();
        }
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}

代码中的问题答案：不会，因为显然val[0]=1.