回文串DP:
首先在原string中加‘*’
k = i + min( mr - i, len[2*mi - i]/2 ) +1 : 中间一项t为以mi为中心与i对称的点j对应的最长回文串(sj)在
点mi对应回文串覆盖范围内的 半长度。
k=i+t+1,直接跳到该位置进行匹配
#include <iostream> #include <stdio.h> using namespace std; char str[1000001]; char buf[2000002]; int len[2000002]; int main(){ int n; cin>>n; for(int casei=0; casei<n; casei++){ scanf("%s", str); if(!str[0]) { cout<<0<<endl; continue; } for(int i=0, j=0; ; i++, j++){ if(!str[i]) {buf[j-1]=0; break;} buf[j]=str[i]; buf[++j]='*'; } len[0]=1; int mr=0, mi=0; for(int i=1; buf[i]; i++){ int k; if(mr>=i){ int j=2*mi-i; // k=i+len[j]/2+1;//error int t = min( len[j]/2, mr-i ); //i+j=2*mi, so j-(2*mi-mr) = mr-i k = i + t + 1; // cout<<i<<":"<<j<<":"<<len[j]<<":"<<k<<endl; } else k=i+1; // k从i回文串右边起点开始,匹配对应左边 for(; buf[k]; k++){ if(2*i-k<0 || buf[2*i-k]!=buf[k]) break; } k--; //k对应i回文串的最右端下标 len[i]=k-(2*i-k)+1; if(k>mr) mr=k, mi=i; } int ml=0, mx=-1; for(int i=0; buf[i]; i++){ int l=len[i]; if(buf[i]=='*') l=(1+l)/4*2; else l=(1+(1+l)/2)/2*2-1; if(ml<l) ml=l, mx=i; } cout<<ml<<endl; } return 0; }