Codeforces D1/D2. Prefix-Suffix Palindrome (字符串hash) /详解

D1. Prefix-Suffix Palindrome (Easy version)
D2. Prefix-Suffix Palindrome (Hard version)

题意：
对于给出的字符串，可截取其前缀和后缀，求能组成的最长回文串。

思路:

正常来说暴力的思路是先匹配前缀pre和后缀suf，找到第一个不匹配的l和r，然后在由l开始从左向右求最长的回文串palindrome，以及由r开始从右向左求最长的回文串palindrome，那么pre+palindrome+suf就是答案。 很显然，这是一个O（n^2）时间复杂度的算法，那么还有哪里可以优化呢？其实关于求回文串palindrome的地方可以优化，据D2的数据来看时间复杂度应该在O(n)或者O(nlogn)，接下来先介绍字符串hash的做法。 对字符串hash不太了解的可以先看： Hash 首先肯定是先把匹配的前后缀长度x求出来，然后由不匹配的地方x+1开始从左向右匹配hash值求最长的回文串palindrome，以及由n-x开始从左向右匹配hash值求最长的回文串palindrome。 最后答案就是s[0…x]+palindrome+s[n-x+1…n]。 感兴趣的话可参考一下这道题的Manacher做法：Manacher做法 如果有什么讲的不清楚的欢迎留言私信交流~

代码:

#include #define ll long long #define ull unsigned long long #define inf 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) #define fi first #define se second #define lowbit(x) (x&(-x)) #define mp make_pair #define pb push_back #define ins insert #define si size() #define E exp(1.0) #define fixed cout.setf(ios::fixed) #define fixeds(x) setprecision(x) #pragma GCC optimize(2) using namespace std; inline ll read(){ll s=0,w=1;char ch=getchar(); while(ch'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch>= 1;}return ans%p;}ll Inv(ll x,ll p){return qp(x,p-2,p);} ll Cal(ll n,ll m,ll p){if (m>n) return 0;ll ans = 1;for(int i = 1; i > s+1; ll n=strlen(s+1); pre[0]=0,suf[n+1]=0,po[0]=1; for(int i=1;i<=n;i++) po[i]=po[i-1]*base%ppp; for(int i=1;i=1;i--) suf[i]=(suf[i+1]*base+s[i]-'a'+1)%ppp; ll l=0,r=0,x=0; while(s[x+1]==s[n-x]&&x+1<n-x) x++; for(int i=x+1;il) l=i-x; for(int i=n-x;i>=x+1;i--) if(ha1(i,n-x)==ha2(i,n-x)) if(n-x-i+1>r) r=n-x-i+1; for(int i=1;i<=x;i++) cout<<s[i]; ll flag=max(l,r); if(flag==l) for(int i=x+1;i<=x+l;i++) cout<=n-x-r+1;i--) cout<<s[i]; for(int i=n-x+1;i<=n;i++) cout<<s[i]; cout<<endl; } return 0; }
作者：别对自己失望

CodeForces d1 hash prefix 字符