Hdu 4763 Theme Section (KMP+暴力或 exKMP)

心已赠人 2022-08-23 12:50 7阅读 0赞

去年比赛时用后缀数组搞了半天没搞出来。。。

用exKMP可以O(n)实现，思路参考自：[hdu 4763 Theme Section (扩展kmp) - No\_\_stop - 博客频道 - CSDN.NET][hdu 4763 Theme Section _kmp_ - No_stop - _ - CSDN.NET]

后面还有份自己写的KMP+暴力枚举的代码

题意：给出一个字符串，问这个字符串的最长Theme Section是多长，Theme Section要符合以下条件，必须出现在字符串的开头，结尾，和中间，而且不能有重叠。  
思路：用扩展kmp可以o（n）的实现,还是先扩展kmp，把next数组处理出来，next\[i\]表示以i为开头的后缀与该字符串的最长公共前缀的长度。对于以长度为i的后缀，若它要能成为答案，那么就要满足在\[i,len-2\*i\]这个区间里找出一个后缀，这个后缀与字符串的最长公共前缀(设长度为mx)要大于等于i。如果把i的长度从大往小的枚举，那么每减小一个长度，区间的左端点就会减1，右端点就会加2，而且区间范围是一直增大的，那么我们就可以在每次询问后，更新mx这个值就好了，整体复杂度只有o（n）。

#include <cstdio>
    #include <cstring>
    #define max(a,b) ((a)>(b)?(a):(b))
    #define max3(a,b,c) (max(a,max(b,c)))
    
    const int N = 1000005 ;
    
    int next[N];
    char str[N];
    
    void exKMP (char t[],int next[])
    {
        int i,j=0,p,L;
        int lent=strlen(t);
        next[0]=lent;
    
        while (j+1<lent && t[j]==t[j+1])
            j++;
        next[1]=j;
        int a=1;
        for (i=2;i<lent;i++)
        {
            p=next[a]+a-1;
            L=next[i-a];
            if (i+L<p+1) next[i]=L;
            else
            {
                j=max(0,p-i+1);
                while (i+j<lent && t[i+j]==t[j])
                    j++;
                next[i]=j;
                a=i;
            }
        }
    }
    
    int main ()
    {
        int T,i;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%s",str);
            exKMP(str,next);
            int n=strlen(str);
            int mx=0,ans=0;//mx保存中间段与前缀重复的最大长度
            for (i=n/3;i<=n-2*(n/3);i++)
                mx=max(mx,next[i]);
            int l=n/3,r=n-2*(n/3);
            for (i=n/3;i>=1;i--)
            {//枚举前缀结尾
                if (next[n-i] == i && mx >= i)
                {
                    ans=i;
                    break;
                }
                l--,r++;
                mx=max3 ( mx , next[l] , next[r] );
                r++;
                mx=max ( mx , next[r] );
            }
            printf ("%d\n",ans);
        }
        return 0 ;
    }

#include<cstring>
    #include<cstdio>
    
    const int N=1000005;
    
    char str[N];
    int next[N];
    
    void getNext(char s[],int len)
    {
        next[0]=-1;
        int i=0,j=-1;
        while (i<len)
        {
            if (j==-1 || s[i]==s[j])
                next[++i]=++j;
            else j=next[j];
        }
    }
    
    int Deal ()
    {
        int len=strlen(str);
        int where=len;
        while (where!=0)
        {
            int tmp=next[where];
            if (3*tmp<=len) for(int i=2*tmp;i<=len-tmp;i++)
                if (next[i]==tmp)
                    return tmp;
            where=next[where];
        }
        return 0;
    }
    
    int main ()
    {
        int T;
        scanf("%d",&T);
        while (T--)
        {
            scanf("%s",str);
            getNext(str,strlen(str));
            printf("%d\n",Deal());
        }
        return 0;
    }

[hdu 4763 Theme Section _kmp_ - No_stop - _ - CSDN.NET]: http://blog.csdn.net/no__stop/article/details/12144075