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

不念不忘少年蓝@ 2021-12-05 16:58 275阅读 0赞

### 题目描述： ###

如果一个字符串正着读和倒着读是一样的，则称它是回文的。  
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少。  
输入格式  
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。  
输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。  
输出格式  
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。  
每个输出占一行。  
输入样例：  
abcbabcbabcba  
abacacbaaaab  
END  
输出样例：  
Case 1: 13  
Case 2: 6

##### 分析： #####

这个题，如果用dp的话，会爆内存。  
所以，我们知道字符串hash可以将一个字符串的字串在O（1）的时间内表示出来。那么，我们可以考虑，以字符串每个位置为中点，向两边延伸，求出以此为中点的最长回文串的长度，并更新ans。在求以此为中点的回文串长度是应该二分来把复杂度降低。

本题wa很久的地方：输入写错 未加+1 导致一个小时的wa。偶数情况写错一点又wa了一会。

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    typedef unsigned long long ull;
    
    ull q[1000010],h1[1000010],h2[1000010];
    int base = 131,Len;
    char str[1000010];
    
    ull get_val_h1(int l,int r)
    {
        return h1[r] - h1[l - 1] * q[r - l + 1];
    }
    
    ull get_val_h2(int l,int r)
    {
        return h2[r] - h2[l + 1] * q[l + 1 - r];
    }
    
    int main()
    {
        q[0] = 1;
        int cnt = 1;
        for(int i = 1; i <= 1000000; i ++)
            q[i] = q[i - 1] * base;
        while(~scanf("%s",str + 1))
        {
            if(strcmp(str + 1,"END") == 0) break;
            Len = strlen(str + 1);
            for(int i = 1; i <= Len; i ++)
                {
                    h1[i] = h1[i - 1] * base + (str[i] - 'a');
                }
            h2[Len + 1] = (ull)0;
            for(int i = Len; i >= 1; i --)
                {
                    h2[i] = h2[i + 1] * base + (str[i] - 'a');
                }
            int ans = 0;
            for(int i = 1; i <= Len; i ++)
            {
                int l = 0,r = min(i - 1,Len - i);
                while(l < r)
                {
    
                    int mid = (l + r + 1) >> 1;
                    ull val_A = get_val_h1(i - mid,i - 1);
                    ull val_B = get_val_h2(i + mid,i + 1);
                    if(val_A == val_B)
                        l = mid;
                    else
                        r = mid - 1;
                }
                ans = max(ans,(l << 1) | 1);
                l = 0,r = min(i - 1,Len - i + 1);
                while(l < r)
                {
                    int mid = (l + r + 1) >> 1;
                    ull val_A = get_val_h1(i - mid,i - 1);
                    ull val_B = get_val_h2(i + mid - 1,i);
                    if(val_A == val_B)
                        l = mid;
                    else
                        r = mid - 1;
                }
                ans = max(ans,l << 1);
            }
            printf("Case %d: %d\n",cnt ++,ans);
        }
    }