回文子串的最大长度 nlogn-Toy模板网

这篇具有很好参考价值的文章主要介绍了回文子串的最大长度 nlogn。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目地址
回文子串模板题

题目描述

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

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

输入格式

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

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

输出格式

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

每个输出占一行。

输入样例：

abcbabcbabcba
abacacbaaaab
END

输出样例：

Case 1: 13
Case 2: 6

算法

求一个字符串中的最长回文子串。采用了哈希判断，其基本思想如下：给定一个字符串，为了方便处理，首先将字符串中的每个字符间都插入一个额外的字符（这里是 ‘z’ + 1）。这样做的好处是原来的回文串有奇数长度与偶数长度，加了额外字符之后只存在奇数长度的回文串。（eg：aba，abba->a#b#a,a#b#b#a, $l e n = 2 s + 1$ ）

然后分别计算字符串从头到尾（ $h l$ ）和从尾到头（ $h r$ ）的哈希值。接着，通过比较从某个位置 $i$ 往两边延伸出去的子串的哈希值，来判断这个子串是否为回文。

判断延伸出去的子串的长度，具有可二分性质，因为在分界点的一侧不满足回文，另一侧满足回文。只要有够区分两侧的性质就可以二分。

具体过程：

输入一个字符串 $s$ ，并计算其长度 $n$ 。在字符串的每个字符间插入一个特殊字符 ‘z’ + 1，得到新的字符串 $s^{'}$ 。新字符串的长度变为 $n := 2 n$ 。
计算字符串 $s^{'}$ 的哈希值 $h l$ 和其逆序字符串的哈希值 $h r$ 。这里， $h l [i]$ 表示的是从字符串 $s^{'}$ 的开头到第 $i$ 个字符的哈希值， $h r [i]$ 表示的是从字符串 $s^{'}$ 的末尾到第 $i$ 个字符的哈希值。
对于每个合法的位置 $i$ ，采用二分的方式找到以 $i$ 为中心的最长回文子串。首先设定搜索的范围为 $\min(i - 1, n - i)]$ ，然后在这个范围内进行二分搜索。假设当前的搜索位置为 $mi d$ ，则需要比较从 $i - mi d$ 到 $i - 1$ 的哈希值 $g e t (h l, i - mi d, i - 1)$ 与从 $n - (i + mi d) + 1$ 到 $n - (i + 1) + 1$ 的哈希值 $g e t (h r, n - (i + mi d) + 1, n - (i + 1) + 1)$ 是否相等。如果这两个哈希值相等，则意味着以 $i$ 为中心，长度为 $mi d$ 的子串是回文的，所以可以继续扩大长度搜索；否则，就需要缩小长度。
1. 关与第二个 $n - (i + mi d) + 1$ 到 $n - (i + 1) + 1$ 的计算，原理是一个字符在 $h l$ 中位置为 $x$ ，在 $h r$ 中位置为 $n - x + 1$ ,所以 $i - mi d$ ， $i - 1$ 对应于 $n - (i + 1) + 1$ ， $n - (i + mi d) + 1$ ，同时由于 $h l$ 中靠左的字符在 $h r$ 中会变成靠右，所以顺序交换
将找到的每个位置 $i$ 的最长回文子串的长度记录下来，并在所有位置中找到最大的长度，记为 $res$ 。注意在记录长度时，如果 $s^{'} [i - l]$ （最左端字符）是原来字符串中的字符，那么长度为 $l + 1$ ，否则长度为 $l$ 。这是因为在字符串的每个字符间都插入了一个额外的字符。#a#b#a和a#b#a这两种情况要分别处理。
最后，输出最长回文子串的长度 $res$ 。

时间复杂度

在这个过程中，哈希值的计算使用了滚动哈希的方法，即每个位置的哈希值都是基于前一个位置的哈希值计算出来的，这样可以在常数时间内得到任意位置的哈希值。另外，比较两个子串是否相等时，也是通过比较它们的哈希值来实现的。搜索时使用二分。所以整个程序的时间复杂度是 $\log n)$ ，其中 $n$ 是字符串的长度。文章来源地址https://www.toymoban.com/news/detail-438312.html

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;
const int N = 2e6 + 10, base = 13331;

char s[N];
ULL hl[N], hr[N], p[N];

ULL get(ULL h[], int l, int r){
    return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
    int T = 1;
    while(scanf("%s", s + 1), strcmp(s + 1, "END"))
    {  // 逗号运算符看最后一项真值
        int n = strlen(s + 1);
        for(int i = 2 * n; i > 0; i -= 2)
        {
            s[i] = s[i / 2];
            s[i - 1] = 'z' + 1;
        }
        n *= 2;
        p[0] = 1;
        for(int i = 1, j = n; i <= n; ++ i, -- j)
        {
            hl[i] = hl[i - 1] * base  + s[i];
            hr[i] = hr[i - 1] * base + s[j];
            p[i] = p[i - 1] * base;
        }
        int res = 0;
        for(int i = 1; i <= n; ++ i)
        {
            int l = 0, r = min(i - 1, n - i);  //  1...i...n
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                if(get(hl, i - mid, i - 1) != get(hr, n - (i + mid) + 1, n - (i + 1) + 1)) r = mid - 1;
                else l = mid;
            }
            int len = 0;
            if(s[i - l] <= 'z') len = l + 1;
            else len = l;
            res = max(res, len);
        }
        printf("Case %d: %d\n", T ++, res);
    }
    return 0;
}