看了官方的题解好像答案只有 n n-1 或 0?
但是我还是决定写出我考试时的做法
首先,子字符串是连续的
根据贪心,我们选取最长的子字符串就是字符串本身
如果字符串本身是回文串怎么办?
那就删掉字符串左边或者右边的一个字符再进行回文串判断即可
那么现在是删掉左边还是右边?我建议你们可以打DFS
由于这个串已经是回文串了,删掉左边和删掉右边的效果其实是一样的
我们循环这个操作,直到找到答案
那么我们最坏需要进行n次回文串判断
暴力判断肯定是要超时的
直接抬出字符串哈希就可以O(1)判断回文串了
参考代码
#include<bits/stdc++.h> #define int long long using namespace std; int n; string a; int ha[10000007]; int hb[10000007]; int p[10000007]; int k=37; bool check(int l,int r) { int m=(r-l+1)/2; return ha[l+m-1]-ha[l-1]*p[m]==hb[r-m+1]-hb[r+1]*p[m]; } signed main() { cin>>a; n=a.length(); a=" "+a; for(int i=1;i<=n;i++) ha[i]=(ha[i-1]*k+a[i]-'a'); for(int i=n;i>=1;i--) hb[i]=(hb[i+1]*k+a[i]-'a'); p[0]=1; for(int i=1;i<=n;i++) p[i]=p[i-1]*k; int l=1,r=n; while((r-l+1)){ if(check(l,r)) l++; else break; } cout<<r-l+1<<"\n"; return 0; }