AcWing 139 回文子串的最大长度(二分，hash ver.)

2020-12-27 15:27

阅读：774

标签：lse 快速 lang sig 回文串 har strlen print ash

题目链接

解题思路

??马拉车当然是求最长回文既简单又快速的方法，不过这里因为要联系hash就没用马拉车了。设回文串的中心为a,b(奇回文a=b)先正着hash一遍，再倒着hash一遍，就能得到[a+len,a]和颠倒后的[b,b+len]两个子串哈希值，对比它们的哈希值就能判断两个子串是否相等，至于len的大小，用二分来判定就行了。

代码

const int maxn = 1e6+10;
char s[maxn];
int n, kase = 1;
unsigned long long f[maxn], rf[maxn], p[maxn] = {1};
int solve(int a, int b) {
    int l = 0, r = min(a-1,n-b);
    while(l>1;
        if (f[a]-f[a-mid-1]*p[mid+1]==rf[b]-rf[b+mid+1]*p[mid+1]) l = mid;
        else r = mid-1;
    }
    return s[a]==s[b] ? l:-1;
}
int main() {
    while(~scanf("%s",s+1) && s[1]!=‘E‘) {
        n = strlen(s+1);
        for (int i = 1; i=1; --i) rf[i] = rf[i+1]*131+s[i]-‘a‘+1;
        int ans = 1;
        for (int i = 2; i

AcWing 139 回文子串的最大长度(二分，hash ver.)

标签：lse 快速 lang sig 回文串 har strlen print ash

原文地址：https://www.cnblogs.com/shuitiangong/p/13337951.html

上一篇：【STM32F429开发板用户手册】第23章 STM32F429的USART串口基础知识和HAL库API

下一篇：KMP字符串-acwing

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing 139 回文子串的最大长度(二分，hash ver.)
文章链接：http://soscw.com/index.php/essay/38617.html

亲，登录后才可以留言！

AcWing 139 回文子串的最大长度(二分，hash ver.)

解题思路

代码

评论

热门文章

推荐文章

最新文章

置顶文章