Codeforces D1/D2. Prefix-Suffix Palindrome (Manacher) /详解
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)，接下来先介绍字符串Manacher的做法。 对字符串Manacher不太了解的可以先看：Manacher 首先肯定是把已经匹配好的前后缀给取出来，那么剩下的中间串重新赋值给另一个字符串，对这个新串进行manacher操作。 Manacher的算法核心就是辅助数组p，p[i]维护回文串的长度。 那么当p[i]==i时说明回文串的起点就是串的起点，而当i+p[i]==len(字符串的长度)时说明回文串的终点就是串的终点，所以我们只要在更新p[i]数组时判断回文串是不是与起点或者终点相连即可。 最后答案就是s[0…x]+palindrome+s[n-x+1…n]。 感兴趣的话可参考一下这道题的hash做法：hash做法 如果有什么讲的不清楚的欢迎留言私信交流~代码:
#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 <= m; ++i)
ans=ans*Inv(i,p)%p*(n-i+1)%p;return ans%p;}
const int manx=1e6+5;
ll len,flag;
void manacher(string s){
ll mx=0,id=0;
vectorp(s.si,0);
for(int i=1;ii+p[i]?min(mx-i,p[2*id-i]):1;
while(s[i+p[i]]==s[i-p[i]]) ++p[i];
if(i+p[i]>mx) id=i,mx=i+p[i];
if(i==p[i]&&len<p[i]) len=p[i]-1,flag=1;
if(i+p[i]==s.si&&len<p[i]) len=p[i]-1,flag=2;
}
}
void init(ll l,ll r,string x){
string s="$#";
for(int i=l;i>s;
ll l=0,r=s.si-1;
while(s[l]==s[r]&&l=r){
cout<<s<<endl;
continue;
}
init(l,r,s);
for(int i=0;i<l;i++) cout<<s[i];
if(flag==1) for(int i=l,j=1;j<=len;i++,j++) cout<<s[i];
else for(int i=r-len+1;i<=r;i++) cout<<s[i];
for(int i=r+1;i<s.si;i++) cout<<s[i];
cout<<endl;
}
return 0;
}
作者：别对自己失望
