[BZOJ2803][Poi2012]Prefixuffix

2803: [Poi2012]Prefixuffix

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 219 Solved: 95
[Submit][Status][Discuss]

Description

对于两个串S1、S2，如果能够将S1的一个后缀移动到开头后变成S2，就称S1和S2循环相同。例如串ababba和串abbaab是循环相同的。
给出一个长度为n的串S，求满足下面条件的最大的L：
1. L<=n/2
2. S的L前缀和S的L后缀是循环相同的。

Input

第一行一个正整数n (n<=1,000,000)。第二行n个小写英文字母，表示串S。

Output

一个整数，表示最大的L。

Sample Input

15
ababbabababbaab

Sample Output

HINT

Source

鸣谢Oimaster

[Submit][Status][Discuss]

这题好厉害啊！！！

设$f[i]=[i+1,n-i]$这个子串中前缀和后缀最长的一样的。

这样答案就=$\max{f[i]+i}，其中[1,i]=[n-i+1,n]$

发现一个性质$f[i-1]<=f[i]+2$，这样就可以类似一个单调栈来$O(n)$处理了。

(PS:POI卡hash，太差了！！)

 #include<cstdio>

 #include<algorithm>

 #define N 1000010

 #define ll long long

 int pow[N][],hash[N][],mod[]={,},n,ans;

 char s[N];

 inline int gethash(int x,int l,int r)

 {return (hash[r][x]-(ll)hash[l-][x]*pow[r-l+][x]%mod[x]+mod[x])%mod[x];}

 inline bool check(int l,int r,int x)

 {

     return gethash(,l,l+x-)==gethash(,r-x+,r)&&gethash(,l,l+x-)==gethash(,r-x+,r);

 }

 int main()

 {

     scanf("%d\n",&n);

     pow[][]=pow[][]=;

     for(int i=;i<=n;i++)

     {

         s[i]=getchar();

         for(int x=;x<=;x++)

         hash[i][x]=((ll)hash[i-][x]*+s[i])%mod[x],

         pow[i][x]=(ll)pow[i-][x]*%mod[x];

     }

     for(int i=n/,j=;i;i--,j=std::min(j+,n/-i))

     if(check(,n,i))

     for(;~j;j--)

     if(check(i+,n-i,j))

     {

         ans=std::max(ans,i+j);

         break;

     }

     printf("%d",ans);

 }

巴特西