最长回文子串问题描述

给定一个字符串，求该字符串中最长的回文字符子串

样例1

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

样例2

输入: "cbbd"
输出: "bb"

问题分析

对于这一问题，最容易想到，也是最容易实现的就是朴素匹配法，即遍历整个字符串，从每一个字符向两侧寻找，并实时更新回文串的长度，如果大于之前求得的最长长度，记录下该字串的头尾坐标。该方法的时间复杂度为O（n³），在此不做解释。对于该问题，可以使用动态规划思想进行优化，试想对于字符串"ababa",如果我们已经知道了"bab"是回文，那么"ababa"一定是回文，因为，两侧的'a'和'a'相等。对于具体实现也不多赘述。下面就是本文的标题所提到的Manacher算法。

Manacher算法介绍

1975 年，一个叫 Manacher 的人发明了一个算法，Manacher 算法，将求解最长回文子串这一问题的时间复杂度降低到了O（n）。

具体代码及注释

/*最长回文字串最佳解决方案，Manacher算法*/
#include <bits/stdc++.h>
using namespace std;

int Max, po, Size, cnt, len[10000000]; //右端点最大值，此时的中点，取到最大值时的下标，最大长度，存储长度
string str1, str2, str3;

void into()
{
    str2 += '@';
    for (int i = 0; i < str1.size(); i++)
    {
        str2 += '#';
        str2 += str1[i];
    }
    str2 += '#';
    str2 += '$';
}

void solve()
{
    for (int i = 1; i <= str1.size() * 2 + 1; i++)
    {
        if (Max > i) //在前串内
            len[i] = min(Max - i, len[2 * po - i]);
        else
        {
            len[i] = 1; //否则重新匹配
        }
        while (str2[i - len[i]] == str2[i + len[i]]) //搜索最大长度
        {
            len[i]++;
        }
        if (i + len[i] > Max) //更新最大右端点及此时中点
        {
            Max = i + len[i];
            po = i;
        }
        cnt = max(cnt, len[i]);
    }
    for (int i = 1; i <= str1.size() * 2 + 1; i++)
    {
        if (cnt == len[i])
        {
            Size = i; //求出取得最大时下标
            break;
        }
    }
    for (int i = Size - cnt + 2; i < Size + cnt; i += 2) //构建子串
    {
        str3 += str2[i];
    }
}

int main(int argc, char *argv[])
{
    cin >> str1;
    into();
    solve();
    cout << str3 << endl;
    system("pause");
    return 0;
}