AcWing 139. 回文子串的最大长度 hash打卡

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

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

输入格式

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

输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。

输出格式

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

每个输出占一行。

输入样例：

abcbabcbabcba

abacacbaaaab

END

输出样例：

Case 1: 13

Case 2: 6

题目：让你找出最长的回文子串

思路：
朴素算法 O(n^2)
枚举中点，然后分奇数长度串，偶数长度串，第二层循环来枚举长度是否可以
哈希做法 O(nlogn)，可优化为O（n）
我们知道哈希可以直接判断字符串是否相等，对于回文的情况我们可以正着求一遍哈希，然后反着再求一边哈希，我们就可以判断任意一个区间是否是回文串
只是我们不确定长度，这里我们可以照着上面的思路，枚举中点，然后二分长度，直接判断是否是回文串。
！！！注意，这里不同上面朴素做法的，上面是必须确定前面才能确定后面是否可以，所以长度必须从1开始遍历，所以我们其实可以省去二分，直接每到新的位置，我们直接从当前最大值+1开始枚举，这样
即时O（n）写法
马拉车算法 O（n）
还没学，菜鸡在此告辞

这里给上我写的哈希做法

#include<bits/stdc++.h>

#define maxn 1000005

#define mod 1000000007

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

char str[maxn];

ull dp1[maxn],f[maxn];

ull dp2[maxn];

ll len;

void hash_code()

{

    memset(f,,sizeof(f));

    memset(dp1,,sizeof(dp1));

    memset(dp2,,sizeof(dp2));

    len=strlen(str+);

    f[]=;

    for(int i=;i<=len;i++){

        dp1[i]=dp1[i-]*+str[i]-'a'+;

        f[i]=f[i-]*;

    }

    for(int i=len;i>=;i--){

        dp2[i]=dp2[i+]*+str[i]-'a'+;

    }

}

int main(){

    ll num=;

    while(scanf("%s",str+)!=EOF){

        if(strcmp(str+,"END")==) break;

        hash_code();

        /*int l,r;

        while(1)

        {

            cin>>l>>r;

            if(dp1[r]-dp1[l-1]*f[r-l+1]==dp2[l]-dp2[r+1]*f[r-l+1]){

                cout<<"YES"<<endl;

            }

            else cout<<"NO"<<endl;

        }*/

        ll mx1=,mx2=;

        for(int i=;i<=len;i++){

            for(int j=mx1+;j<=len;j++){

                if(i+j>len||i-j<=) break;

                if(dp1[i+j]-dp1[i-j-]*f[*j+]!=dp2[i-j]-dp2[i+j+]*f[*j+]) break;

                mx1++;

            }

            for(int j=mx2+;j<=len;j++){

                if(i+j>len||i-j+<=) break;

                if(dp1[i+j]-dp1[i-j]*f[*j]!=dp2[i-j+]-dp2[i+j+]*f[*j]) break;

                mx2++;

            }

            //printf("%lld:%lld\n",i,mx1+1);

        }

        printf("Case %lld: %lld\n",num++,max(*mx1+,*mx2));

    }

}

巴特西

AcWing 139. 回文子串的最大长度 hash打卡

输入格式

输出格式

输入样例：

输出样例：

最新文章

热门文章