分析性质以进行DP
性质1：一定有一个最优解通过每次删除第一个或最后一个字符达到
这个脑补一下就能证明了
那么我们设$dp[i]$表示后缀$[i,n]$选出一个前缀所能达到的最大长度，从右往左DP
转移时二分当前DP值$dp[i]$，在右边找有没有大于等于$f_i-1$且是$[i,n]$前缀/后缀的DP值，具体怎么找就看个人了
可以不二分吗？可以，继续分析得到性质2
性质2：dp[i]<=dp[i+1]+1
反证，如果$dp[i]>dp[i+1]+1$，那么删掉第一个字符，就会得到$dp[i+1]>dp[i+1]+1-1$
然而不想(hui)写后缀结构的我选择了暴力查哈希，因为答案不会超过$sqrt n$，所以从小到大枚举长度做即可 
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define uint unsigned int 5 using namespace std; 6 const int N=500005; 7 const uint mod=7539151; 8 bool p1[N],p2[N],mp[mod+1]; 9 uint hsh[N]; char str[N]; int n; 10 int main() 11 { 12 register int i,j; 13 scanf("%d%s",&n,str+1); 14 bool *dp=p1,*pd=p2; 15 int ans=1,lim=min(1000,n); 16 for(i=1;i<=n;i++) 17 hsh[i]=str[i]-'a'+1,pd[i]=true; 18 for(i=2;i<=lim;swap(dp,pd),i++) 19 { 20 memset(dp,0,sizeof p1); 21 memset(mp,0,sizeof mp); 22 for(j=n-i+1;j;j--) 23 { 24 if(j+i<=n&&pd[j+i]) mp[hsh[j+i]]=true; 25 if(mp[hsh[j]]||mp[hsh[j+1]]) ans=i,dp[j]=true; 26 } 27 for(j=1;j<=n-i+1;j++) 28 hsh[j]=(hsh[j]*233+str[j+i-1]-'a'+1)%mod; 29 } 30 printf("%d",ans); 31 return 0; 32 }