Manacher：
复杂度：
O(n)
基本问题：求字符串的最长回文子串
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std ;
const int maxn =
1e6 +
10 ;
char S[maxn] ;
char ma[maxn *
2 +
1] ;
int mp[maxn *
2 +
1] ;
void manacher(
int len ){
int l =
0 ;
ma[l++] =
'S' ;
ma[l++] =
'#' ;
for(
int i =
0 ;i<len;i ++ ){
ma[l++] = S[i] ;
ma[l++] =
'#' ;
}
int mx =
0 , id =
0 ;
for(
int i =
0 ;i<l ;i ++){
mp[i] = mx>i ? min(mp[
2* id - i] , mx - i) :
1 ;
while( ma[ i + mp[i] ] == ma[ i - mp[i] ] ) mp[i]++ ;
if(i +mp[i] > mx){
mx = i + mp[i] ;
id = i ;
}
}
}
int main(){
int a;
cin>>a ;
getchar();
while(a--){
gets(S) ;
int len =
strlen(S) ;
manacher(len) ;
int ans =
0 ;
for(
int i =
0 ;i<
2*len +
2 ;i++){
ans = max(ans , mp[i] -
1 ) ;
}
printf(
"%d\n" , ans) ;
}
return 0 ;
}
