描述

题目描述

给定我们一个字符串，然后让我们求取出来我们的这个字符串的最大回文子串，回文就是对折之后两半都是一样的，子串的概念就是我们可以在开头或者是结尾删除一些元素，就是一个子串

题解

解法一：纯纯大暴力

实现思路

我们可以考虑直接枚举所有可能出现的开头的位置和所有可能出现的结尾的位置，然后我们每次对这样的一个字符串进行一个判断是否是回文字符串，如果是的话，我们时刻更新我们的最长的回文子串的一个长度，然后最后输出

代码实现

#include <bits/stdc++.h>

using namespace std;

bool check(string s, int l, int r) {
    for (; l < r; l++, r--)
        if (s[l] != s[r]) return false;
    return true;
    // 这里我们判断一个字符串是不是回文串
}

signed main() {
    string s;
    cin >> s;
    int maxx = INT_MIN;
    // 这个maxx是我们的最长回文子串的一个长度
    for (int i = 0; i < s.size(); i++) {
        // 我们第一层循环枚举的是我们这个字符串的一个起点的位置
        for (int j = i; j < s.size(); j++) {
            // 我们的第二层循环是用来循环我们的结尾的位置是在哪里的
            if (check(s, i, j)) {
                maxx = max(maxx, j - i + 1);
                // 如果我们当前的这个字符串是回文串，我们更新一下最大的长度
            }
        }
    }
    cout << maxx << "\n";
    return 0;
}

时空复杂度分析

时间复杂度： $O(n^3)O(n\; ^\; 3)$

理由如下：首先我们判断一个字符串是不是回文字符串的时间复杂度是$O(n)O(n)$的，然后我们接下来两层$forfor$循环枚举我们的所有开头和结尾，然后这个就是$O(n^2)O(n\; ^\; 2)$的时间复杂度，最后他们是一个包含的关系，最后的时间复杂度就是$O(n^3)O(n\; ^\; 3)$的

空间复杂度： $O(1)O(1)$

理由如下：我们只引用了常数级别的空间

解法二：Manacher算法

实现思路

我们想要求取最长回文子串的话, 我们这里给出专门解决这个问题的一个方法就是$ManacherManacher$算法, 当然我们也可以使用二分加哈希或者后缀数组和快速$LCALCA$来做, 但是这里我们引入一个时间和空间上有更小常数的$ManacherManacher$算法

首先我们可以肯定的第一点就是我们的字符串一共是两种, 一种是偶数串, 一种是奇数串, 这给我们求取最长回文子串造成了困难, 那么我们可以把我们的偶数串和奇数串统一变成奇数串, 如何实现呢? 如图所示

我们可以保证这个字符串就是奇数长度的

然后我们可以得到转换过后的一个性质: $xx$长度的回文串转换后得到的回文串半径为$x+1x\; +\; 1$

然后我们记录$p[i]p[i]$指以$sisi$为中心的最大回文串的半径长度

我们求取$p[i]p[i]$: 从前向后遍历, 同时维护一个有边界最靠右的回文串, 记录其$midmid$和$max-rightmax-right$递推到$ii$时, 找$ii$关于$midmid$的对称点$j=2\ast mid-1j\; =\; 2\; *\; mid\; -\; 1$, 有这么一个图参考

如果我们的$ii$在$(mid,mr)(mid,\; mr)$之间, $p[i]==min(p[j],mr-i)p[i]\; ==\; min(p[j],\; mr\; -\; i)$

若我们的$ii$在$[mr,+\mathrm{\infty })[mr,\; +\backslash infty)$处, $p[i]=1p[i]\; =\; 1$然后我们暴力扩张同时更新$mrmr$

然后我们可以书写我们的代码了

代码实现

#include <bits/stdc++.h>

using namespace std;

string init(string &s) {
    string res = "";
    res += "$#";
    for (int i = 0; i < s.size(); i++) res += s[i], res += '#';
    res += '^';
    return res;
    // 这个是在开始和结束加上通配符, 然后我们中间每个分割的地方加上#
}

void manacher(vector<int> &p, string &s) {
    int mr = 0, mid;
    // mr代表以mid为中心的最长回文的有边界
    // mid为i和j的中心点, i以mid为对称点翻折到j的位置
    for (int i = 1; i < s.size(); i++) {
        if (i < mr)
            p[i] = min(p[mid * 2 - i], mr - i); 
        // 2 * mid - i为i关于mid的对称点
        else
            p[i] = 1;
        // 超过边界总共就不是回文了
        while (s[i - p[i]] == s[i + p[i]]) p[i]++;
        // 不需要判断边界, 因为我们有通配符
        if (i + p[i] > mr) {
            mr = i + p[i];
            mid = i;
        }
        // 我们每走一步i, 都要和mx比较, 我们希望mx尽可能的远
    }
}

signed main() {
    string s;
    cin >> s;
    s = init(s);
    vector<int> p(s.size());
    manacher(p, s);
    // 初始化字符串和求取出来我们的每一个位置的最长长度
    int maxx = INT_MIN;
    for (auto &it : p) maxx = max(maxx, it);
    cout << maxx - 1 << "\n";
    return 0;
}

时空复杂度分析:

时间复杂度: $O(n)O(n)$

理由如下: 我们的内层循环有两种情况, 如果我们的$ii$在内部, 我们$whilewhile$的次数是小于等于$ii$的, 如果$ii$在边界, 那么我们向外扩张的时候右边界是单调的, 我们运行的过程中从不减少, 这个是线性的, 所以我们的时间复杂度就是$O(n)O(n)$的

空间复杂度: $O(n)O(n)$

理由如下: 我们其他地方也就是扩展了我们的字符串, 也就是扩展大概$22$倍左右, 其实也是$O(n)O(n)$级别的