牛客题霸 [ 最长回文子串] C++题解/答案

题目描述

对于一个字符串,请设计一个高效算法,计算其中最长回文子串的长度。

给定字符串A以及它的长度n,请返回最长回文子串的长度。

题解:

两个方法:
一个是经典暴力,这个大家应该都会
还一个是manacher(马拉车)
马拉车是专门处理回文串的算法
介绍两个变量
id:回文子串的中心位置
mx:回文子串的最后位置

p[i] = min(mx-i, p[2 * id - i])

p[i]:以i为中心的回文半径长度

当前,我们已经得到了 p[0…i-1],想要计算出 p[i] 来。
红1为以 j 为中心的回文子串,红2为以 i 为中心的回文子串,红3为以 id 为中心的回文子串(首尾两端分别为mx的对称点和mx)。

那么,如果 mx 在 i 的右边,则我们可以通过已经计算出的 p[j] 来计算 p[i],其中 j 与 i 的中心点为 id。这里分两种情况:

先直接令 p[i] 的回文子串就等于 p[j] 的回文子串,即红2长度等于红1,然后判断红2的末尾是否超过了 mx,如果没有超过,则说明 p[i] 就等于 p[j]。
为什么呢?
因为以 id 为中心的回文子串为红3,包含了红1和红2,而且红1和红2以 id 为中心,那么一定有红2=红1。并且已经知道,红1是以 j 为中心的最长子串,那么红2也肯定是以 i 为中心的最长子串。
如果红2的末尾超过了 mx,那么就只s能让 p[i] = mx - i了,即我可以保证至少半径到 mx 这个位置,是可以回文的,但是一旦往右超出了 mx,就不能保证了,剩下的只能用笨方法慢慢扩张来得到最长回文子串。
那如果红2的左边超出了mx的对称点,怎么办?不会出现这种情况的,因为红1的右边不会超过mx。如果超过了mx,那么在上一次迭代中,id应该更新为j,mx应该更新为 j+p[j]。在迭代中,会始终保证 mx 是所有已经得到的回文子串末端最靠右的位置。

另外,如果 mx 不在 i 的右边呢?那就利用不了红3的对称性了,只能使用笨方法慢慢扩张了。

代码:

class Palindrome {
   
public:
    int p[100010], id = 0, mx = -1, maxx = -1;
    int getLongestPalindrome(string A, int n) {
   
        // write code here
        string str = "@#";
        for ( int i = 0; i < n; i++ ) {
   
            str += A[i];
            str += '#';
        }
        for ( int i = 0; i < str.size(); i++ ) {
   
            if ( i < mx ) p[i] = min(p[ id * 2 - i], mx - i);
            else p[i] = 1;
            while ( str[i-p[i]] == str[i + p[i]]) p[i]++;
            if ( p[i] + i > mx) {
   
                id = i;
                mx = p[i] + i;
            }
            maxx = max(maxx, p[i]-1);
        }
        return maxx;
    }
};