---
title: "回文串的最大长度"
created: 2025-11-28
tags:
  - 算法
---

# 回文串的最大长度

## 题目 [回文子串的最大长度](https://www.acwing.com/problem/content/description/141/)

![[image-4f98cc80.png]]

## 思路分析

首先回文串问题可以想到之前的[[小牛快传|小牛快传]]

利用中心拓展算法写

实践证明是可行的 但是会tle 差一个数据

那就想其他办法

为什么超时 时间花在了哪 首先枚举每个点是必不可少的

时间主要浪费在了对于每个点 都做双指针向左向右找到边界（这就像单调栈里那个直方图最大面积一样）

所以要想办法减少对每个点来说 找到最左最右边界的情况

回文串可以抽象成 对每个点 做一次对折 我们要找的是以它为中心拓展的长度的最大值

实际就是对每个点 对折后的左右两边进行匹配的问题

![[image-ca7dca3b.png]]

可以直接把字符串拷贝一份 翻转一下  然后对这两个串 枚举每个点 去找最长匹配

![[image-d0710797.png]]

显然这种匹配不就有什么前缀性 分段性 那就直接用字符串哈希了

![[image-96b99336.png]]

然后发现这个半径显然是可以用二分来求的 如果两个不相等 就说明mid取大了

所以问题变成了 **枚举中点 二分半径 维护最大值**

但是还有一个问题 在之前的做法里也考虑过

回文串是分为两种的 一种是奇数的 我们可以用上述考虑的方法 枚举中点

但是 偶数呢 中点是在两个字符的缝隙中 双指针可以调整枚举位置解决这个问题

但是这种方式 我们就得再为偶数的情况分析一次了

或者想办法 把偶数的情况也变成奇数

![[image-f2b71f7c.png]]

在每两个字符中间 插入一个其他字符 这样奇数不受影响 偶数也变成了奇数

那问题就好解决了

现在就是额外注意一下下标问题就好了

在匹配里 这个不造成任何影响 因为中间插的是相同的字符 匹配结果还是对的

也不会影响答案 因为我们要的答案是二分出来的那个r

r是半径 原本是要乘上2才是答案的 但是因为我们在每俩字符中间插了一个#

所以不需要乘2了 我们只需关心i-r位置上是字母还是#

是字母的话是r+1

是#的话 结果就是r

![[image-aed687d2.png]]

## 代码实现

**中心拓展（双指针）tle**

```cpp
#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;
}
```

**字符串哈希+二分**

```cpp
#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;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[后缀数组|后缀数组]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/串相关模型/字符串哈希/矩阵|矩阵]]