AcWing 139. 回文子串的最大长度(字符串哈希 + 二分)
原题链接
中等
作者:
tom233
,
2021-01-31 22:20:11
,
所有人可见
,
阅读 1261
思路:从前往后求字符串前缀的哈希值hl
,从后往前求字符串后缀的哈希值hr
。然后枚举回文串的中点,再求回文串的最大半径。因为求最大半径最有单调性,即大的半径是回文串则小的半径一定是回文串,所以半径的长度可以用二分法来求,这样求每个中点的半径只需O(logn)的复杂度,枚举n个中点,所以总的时间复杂度是O(nlogn)。
另外回文串有可能是偶数也可能是奇数,得分情况讨论。可以在每个字符之间加入一个不在字符串中的字符,来使得字符串变成奇数,2 * n - 1 = n + n - 1
。还得注意求后缀哈希值时,下标在右的,在hr
中的相对位置为左
还可以用马拉车算法,时间复杂度为线性
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 2e6 + 10 , base = 131;
ULL hr[N] , hl[N] , p[N];
char str[N];
ULL get(ULL h[] , int l , int r)
{
return h[r] - h[l - 1] * p[r + 1 - l];
}
int main()
{
int T = 1;
while(cin >> str + 1 , strcmp(str + 1 , "END"))
{
int n = strlen(str + 1), res = 0;
for(int i = 2 * n ; i >= 0 ; i -= 2)
{
str[i] = str[i / 2];
str[i - 1] = 'z' + 1;
}
n *= 2; p[0] = 1;
for(int i = 1 , j = n; i <= n ; i ++ , j -- )
{
p[i] = p[i - 1] * base;
hl[i] = hl[i - 1] * base + str[i];
hr[i] = hr[i - 1] * base + str[j];
}
for(int i = 1 ; i <= n ; i ++ )
{
int l = 0 , r = min(n - i , i - 1);
while(l < r)
{
int mid = l + r + 1 >> 1;
if(get(hl, i - mid, i - 1) == get(hr, n + 1 - (i + mid), n + 1 - (i + 1)))l = mid;
else r = mid - 1;
}
if(str[i - l] <= 'z')res = max(res , l + 1);
else res = max(res , l);
}
printf("Case %d: %d\n",T ++ , res);
}
return 0;
}
’‘’cpp
if(str[i - l] <= ‘z’)res = max(res , l + 1);
‘’‘
这一行里的str[i - l] 是啥
请问
p[i] = p[i - 1] * base;
hl[i] = hl[i - 1] * base + str[i];
hr[i] = hr[i - 1] * base + str[j];
这三行乘以base是什么意思啊
预处理哈希值,基础课中有说