题目链接

算法竞赛进阶指南-53.回文子串的最大长度

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为 $N$ 的字符串 $S$，求他的最长回文子串的长度是多少。

输入格式

输入将包含最多 $30$ 个测试用例，每个测试用例占一行，以最多 $1000000$ 个小写字符的形式给出。

输入以一个以字符串 END 开头的行表示输入终止。

输出格式

对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

Method1 : 字符串哈希 + 二分

递推枚举回文子串的中点，然后用二分法判断两边边界的最大长度

这道题挺恶心的，如果是cin读取字符串会TLE，必须手动开O2优化才能过。

#pragma GCC optimize(2)

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 7;
const int P = 131;

vector<ULL> p(N * 2);

vector<ULL> get_prefix_hash(const string& s) {
    int n = s.size();
    vector<ULL> h(n + 1);
    h[0] = 0;
    p[0] = 1;
    for (int i = 1; i <= n; i ++) {
        h[i] = h[i - 1] * P + s[i - 1];
        p[i] = p[i - 1] * P;
    }
    return h;
}

ULL get_substr_hash(const vector<ULL>& h, int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() {
    string s;
    int T = 1;
    while (cin >> s, s != "END") {
        int n = s.size();
        s.resize(n * 2);
        for (int i = n * 2 - 1; i >= 0; i -= 2) {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }
        n = n * 2;
        // for (int i = 0; i < n; i ++) {
        //     cout << s[i] ;
        // }
        // cout << endl;
        
        vector<ULL> hl = get_prefix_hash(s);
        reverse(s.begin(), s.end());
        vector<ULL> hr = get_prefix_hash(s);
        reverse(s.begin(), s.end()); // reverse(回来)
        
        int res = 0;
        for (int i = 1; i <= n; i ++) {
            int l = 0, r = min(i - 1, n - i); // 二分最大半径mid
            while (l != r + 1) {
                int mid = l + r >> 1;
                if (get_substr_hash(hl, i - mid, i - 1) != get_substr_hash(hr, n - (i + mid) + 1, n - (i + 1) + 1)) {
                    r = mid - 1;
                }
                else {
                    l = mid + 1;
                }
            }
            
            if (s[i - r + 1] <= 'z') res = max(res, r + 1);
            else res = max(res, r);
        }
        
        printf("Case %d: %d\n", T ++, res);
        
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：${O(n + \log n)}$， 其中reverse的时间和预处理前缀的时间都是$O(n)$ ，$O(\log n)$为二分。

• 空间复杂度：${O(N * 2)}$，花$O(N)$的空间存储$P$的$N$次幂。

Method2：Manacher

这题也可以用manacher做，复杂度是O（N）

复杂度分析