hihoCoder week1 最长回文子串

时间:2022-06-08 12:18:14

题目链接

https://hihocoder.com/contest/hiho1/problem/1

做法 Manacher

#include <bits/stdc++.h>
using namespace std; #define Max(a,b) ((a>b)?a:b)
const int N = 1e6 + ;
char s[N], c[N*]; int dp[N*]; // 以i为中心的 回文半径 void init(int len)
{
c[]='$';
for(int i=;i<=len;i++){
c[i*-]='#';
c[i*]=s[i];
}
c[*len+]='#';
c[*len+]='\0';
} int manacher(int len)
{
memset(dp, , sizeof(dp));
int l = * len + ;
int pos=,R=,mx=;
// printf(" ");
for(int i=; i<=l; i++) {
if(i < R)
dp[i]=min(dp[*pos-i], R-i);
else
dp[i]=;
while( <=i-dp[i] && i+dp[i]<=l && c[i-dp[i]] == c[i+dp[i]] )
dp[i]++;
if(i+dp[i] > R) {
R = i + dp[i];
pos = i;
}
mx = Max(mx, dp[i]-);
// printf("%d",dp[i]);
}
//ans = mx;
return mx;
}
int main()
{
freopen("in.txt","r",stdin);
int T; scanf("%d", &T);
while(T--) {
scanf(" %s", s+);
int len = strlen(s+);
init(len);
// cout << c <<endl;
cout << manacher(len) <<endl;
}
return ;
}