3648. 【GDOI2014】beyond (Standard IO)

Time Limits: 

1000 ms  Memory Limits: 262144 KB     

Description

 

Input

第一行：包含一个整数N。

第二行：包含一个长度为N的字符串，字符串中只包含小写字母。

第三行：包含一个长度为N的字符串，字符串中只包含小写字母。

Output

输出答案只包含一个数字L，表示圆环最大可能有的格子数。

 

Sample Input

输入1：

5

abcdx

cdabz

输入2：

4

abcd

cdab

Sample Output

输出1：

4

输出2：

4

 

Data Constraint

对于20% 的数据，1 <= N <= 5,000

对于50% 的数据，1 <= N <= 600,000

对于100% 的数据，1 <= N <= 2,000,000

 

思路：

先做两次扩展KMP，求出 a的后缀匹配b的最长长度exA[i]和b的后缀匹配a的最长长度exB[i]

枚举长度L

在KMP中加些处理求出以A[I]为结尾的后缀中与B匹配的最长长度j，再判断j和它的next中最大的j+exB[j+1]（KMP+DP预处理）如果大于L，则L为可行解

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int s1[2000222],s2[2000222],a[2000222],b[2000222];int exA[2000222],exB[2000222],next[2000222];int dp[2000222],dp2[2000222];int m,n,i,t,xzq,l;char c;void Read(int *s){    m=0;    while(c=getchar(),c<'a'||c>'z');    s[++m]=c;    while(c=getchar(),c>='a'&&c<='z')s[++m]=c;}void Exkmp(){    int len,l,k,i;    memset(a,0,sizeof(a));    memset(b,0,sizeof(b));    len=0;    k=0;    for(i=2;i<=n;i++){        if(len
          
           len){ len=i+a[i]-1; k=i; } } len=0; k=0; for(i=1;i<=n;i++){ if(len
           
            dp[i+l])dp[i+l]=l+1; l++; } b[i]=l; } else{ if(a[i-k+1]
            
             dp[i+l])dp[i+l]=l+1; l++; } b[i]=l; } } if(i+b[i]-1>len){ len=i+b[i]-1; k=i; } }}void Kmp(){ int i,j,x; memset(next,0,sizeof(next)); x=0; for(i=2;i<=n;i++){ while(x!=0&&s1[i]!=s1[x+1])x=next[x]; if(s1[i]==s1[x+1])x++; next[i]=x; if(dp2[x]>dp2[i])dp2[i]=dp2[x]; }}int main(){ scanf("%d",&n); Read(s1); Read(s2); Exkmp(); for(i=1;i<=n;i++)exB[i]=b[i]; for(i=1;i<=n;i++){ t=s1[i]; s1[i]=s2[i]; s2[i]=t; } memset(dp,0,sizeof(dp)); Exkmp(); for(i=1;i<=n;i++)exA[i]=b[i]; for(i=1;i<=n;i++)dp2[i]=i+exB[i+1]; Kmp(); for(i=1;i<=n;i++){ l=dp[i]; if(dp2[l]>=i)xzq=i; } printf("%d\n",xzq);}