回文串的最大长度
题目 回文子串的最大长度
思路分析
首先回文串问题可以想到之前的小牛快传
利用中心拓展算法写
实践证明是可行的 但是会tle 差一个数据
那就想其他办法
为什么超时 时间花在了哪 首先枚举每个点是必不可少的
时间主要浪费在了对于每个点 都做双指针向左向右找到边界（这就像单调栈里那个直方图最大面积一样）
所以要想办法减少对每个点来说 找到最左最右边界的情况
回文串可以抽象成 对每个点 做一次对折 我们要找的是以它为中心拓展的长度的最大值
实际就是对每个点 对折后的左右两边进行匹配的问题
可以直接把字符串拷贝一份 翻转一下 然后对这两个串 枚举每个点 去找最长匹配
显然这种匹配不就有什么前缀性 分段性 那就直接用字符串哈希了
然后发现这个半径显然是可以用二分来求的 如果两个不相等 就说明mid取大了
所以问题变成了 枚举中点 二分半径 维护最大值
但是还有一个问题 在之前的做法里也考虑过
回文串是分为两种的 一种是奇数的 我们可以用上述考虑的方法 枚举中点
但是 偶数呢 中点是在两个字符的缝隙中 双指针可以调整枚举位置解决这个问题
但是这种方式 我们就得再为偶数的情况分析一次了
或者想办法 把偶数的情况也变成奇数
在每两个字符中间 插入一个其他字符 这样奇数不受影响 偶数也变成了奇数
那问题就好解决了
现在就是额外注意一下下标问题就好了
在匹配里 这个不造成任何影响 因为中间插的是相同的字符 匹配结果还是对的
也不会影响答案 因为我们要的答案是二分出来的那个r
r是半径 原本是要乘上2才是答案的 但是因为我们在每俩字符中间插了一个#
所以不需要乘2了 我们只需关心i-r位置上是字母还是#
是字母的话是r+1
是#的话 结果就是r
代码实现
中心拓展（双指针）tle
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
PII findLongestPalindrome(const string& s, int left, int right) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
left--;
right++;
}
return {left + 1, right - 1};
}
int main()
{
string str;
int nowcase=0;
while (cin>>str && str.substr(0,3)!="END") {
++nowcase;
int start = 0, end = 0;
for (int i = 0; i < str.size(); ++i)
{
auto [left1, right1] = findLongestPalindrome(str, i, i);
auto [left2, right2] = findLongestPalindrome(str, i, i + 1);
if (right1 - left1 > end - start) {
start = left1;
end = right1;
}
if (right2 - left2 > end - start) {
start = left2;
end = right2;
}
}
cout<<"Case "<<nowcase<<": " << end - start + 1 << endl;
}
return 0;
}
字符串哈希+二分
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N=2000010,P=131;
char str[N];
ULL ho[N],hr[N],p[N];
ULL find(ULL h[],int l,int r){
return h[r]-h[l-1]*p[r-l+1];
}
int main()
{
int nowcase=0;
while(cin>>str+1 && strcmp(str+1,"END")){
++nowcase;
int n=strlen(str+1);
n*=2;
for(int i=n;i>0;i-=2){
str[i]=str[i/2];
str[i-1]='#';
}
p[0]=1;
for(int i=1,j=n;i<=n,j>=1;i++,j--){
ho[i]=ho[i-1]*P+str[i];
hr[i]=hr[i-1]*P+str[j];
p[i]=p[i-1]*P;
}
int res=0;
for(int i=1;i<=n;i++){
int l=0,r=min(i-1,n-i);
while(l<r){
int mid=l+r+1>>1;
if(find(ho,i-mid,i-1)==find(hr,n-(i+mid)+1,n-(i+1)+1))
l=mid;
else
r=mid-1;
}
if(isalpha(str[i-r]))
res=max(res,r+1);
else
res=max(res,r);
}
cout<<"Case "<<nowcase<<": " << res << endl;
}
return 0;
}
💬 评论