AcWing 1524. 最长回文子串
原题链接
简单
作者:
zanyyan123
,
2024-03-14 10:21:01
,
所有人可见
,
阅读 11
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
typedef unsigned long long ULL;
const int P = 13331;
int h[N], h2[N], p[N];
string str, str2;
int n;
ULL get(int l, int r){
return h[r] - h[l - 1] * p[r - l + 1];
}
ULL get2(int l, int r){
return h2[r] - h2[l - 1] * p[r - l + 1];
}
bool check(int x){
if(x <= 0 || x > n) return false;
for(int l = 1; l + x - 1 <= n; l++){
int r = l + x - 1;
if(get(l, r) == get2(n - r + 1, n - l + 1)){
return true;
}
}
return false;
}
signed main(){
getline(cin, str);
n = str.size();
str = " " + str;
str2 = str;
reverse(str2.begin() + 1, str2.end());
// cout<<str<<"\n"<<str2<<"\n";
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + str[i];
h2[i] = h2[i - 1] * P + str2[i];
}
// cout<<get(1, 5)<<" "<<get2(2, 6)<<"\n";
int ans = 0;
bool f = false;
int l = 1, r = n/2;
while(l < r){
int mid = (l + r + 1) >> 1;
if(check(2 * mid)){
l = mid;
}
else{
r = mid - 1;
}
}
if(check(2 * l)) ans = 2 * l;
l = 0, r = n/2;
while(l < r){
int mid = (l + r + 1) >> 1;
// cout<<"mid = "<<mid<<"\n";
if(check(2 * mid + 1)){
l = mid;
}
else{
r = mid - 1;
}
}
ans = max(ans, 2 * l + 1);
cout<<ans<<"\n";
return 0;
}