哪个协会要做网站建设啊,网站一般要设计几页,wordpress评论自定义头像,城乡与建设部网站首页P4445 最长回文串
题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如acbcaacbcaacbca是回文串#xff0c;而abcabcabc不是#xff08;abc的顺序为abcabcabc#xff0c;逆序为cbacbacba#xff0c;不相同#xff09;。
输入长度为nnn的串SSS#xff0c;求SSS的最…P4445 最长回文串
题目描述
顺序和逆序读起来完全一样的串叫做回文串。比如acbcaacbcaacbca是回文串而abcabcabc不是abc的顺序为abcabcabc逆序为cbacbacba不相同。
输入长度为nnn的串SSS求SSS的最长双回文子串TTT,即可将TTT分为两部分XXXYYY∣X∣,∣Y∣≥1∣X∣,∣Y∣≥1|X|,|Y|≥1∣X∣,∣Y∣≥1∣X∣,∣Y∣≥1∣X∣,∣Y∣≥1且XXX和YYY都是回文串。
题目解答
将串sss进行预处理增加’$‘和’#字符得到nsnsns串以便使用Manacher算法.
使用Manacher算法求以每个位置为中心的最长回文串长度数组npnpnp.
算法一.
根据数组ppp,处理出数组lft,rgtlft,rgtlft,rgt
lft[i]lft[i]lft[i]表示nsnsns中以iii为右端点的最长回文串的中心位置.
rgt[i]rgt[i]rgt[i]表示nsnsns中以iii为左端点的最长回文串的之心位置.
ps:由于nsnsns字符串中包含了#\##字符,因此回文串中心到一端的距离,就可以实际表示一个回文串的长度.
由于nsnsns串特殊的奇偶性,我们枚举iii,计算rgt[i1]−lft[i]{rgt[i1]-lft[i]}rgt[i1]−lft[i]的最大值就是答案.
问题变成了如何求lft,rgtlft,rgtlft,rgt数组.
以lftlftlft为例,rgtrgtrgt求法类似:
枚举回文串中心的位置iii,则lft[i,inp[i])lft[i,inp[i])lft[i,inp[i])区间内未设置值得位置全都设置成为iii.
实现代码
#include iostream
#include cstdio
#include queue
#include vector
#include cstringconst int N 100007;
char s[N],ns[N1];int np[N1];#define pr(x) std::cout #x : x std::endlstd::vectorint vec[N1];
int vis[N1];int lft[N1],rgt[N1];int Manacher() {int len 0,mx 0,id;ns[len] $;ns[len] #;for(int i 0;s[i];i)ns[len] s[i],ns[len] #;for(int i 1;i len;i) {np[i] mx i ? std::min(np[2*id-i],mx-i):1;while(ns[i-np[i]] ns[inp[i]]) np[i];if(np[i]i mx) mx np[i]i,id i;}int p 0;for(int i 0;i len;i) {for(;p i np[i];p) {lft[p] i;}} p len;for(int i len-1;i 0;--i) {for(;p i - np[i];--p) {rgt[p] i;}}int ans 0;for(int i 1;i len;i) {ans std::max(ans,rgt[i1] - lft[i]);} return ans;
}int main() {std::cin s;std::cout Manacher() std::endl;return 0;
}算法二.
计算数组lft,rgtlft,rgtlft,rgt
lft[i]lft[i]lft[i]表示以iii为右端点的最长回文子串在sss中的实际长度.
rgt[i]rgt[i]rgt[i]表示以iii为左端点的最长回文子串在sss中的实际长度.
那么答案就是枚举iii为偶数,ansmax(lft[i]rgt[i2])ans max(lft[i] rgt[i2])ansmax(lft[i]rgt[i2])
以lftlftlft为例,rgtrgtrgt类似:
从小到大枚举iii,并用一个优先队列维护当前最小的回文串中心点iii,设定在inp[i]inp[i]inp[i]位置将优先队列中的iii设为失效.
每次从优先队列中取出的第一个有效的数即是lft[i]lft[i]lft[i].
这种算法的思路与算法一本质上是一样的,只不过枚举量不同,算法一枚举的是lft[i]lft[i]lft[i],然后利用单调性将时间复杂度降低到了O(n)O(n)O(n)
算法二枚举的是iii,需要用数据结构来维护,时间复杂度是O(nlogn)O(nlogn)O(nlogn)
#include iostream
#include cstdio
#include queue
#include vector
#include cstringconst int N 100007;
char s[N],ns[N1];int np[N1];#define pr(x) std::cout #x : x std::endlstd::vectorint vec[N1];
int vis[N1];int lft[N1],rgt[N1];int Manacher() {int len 0,mx 0,id;ns[len] $;ns[len] #;for(int i 0;s[i];i)ns[len] s[i],ns[len] #;for(int i 1;i len;i) {np[i] mx i ? std::min(np[2*id-i],mx-i):1;while(ns[i-np[i]] ns[inp[i]]) np[i];if(np[i]i mx) mx np[i]i,id i;}for(int i 0;i (N 1);i) vec[i].clear();memset(vis,0,sizeof(vis)); std::priority_queueint,std::vectorint,std::greaterint lQ;for(int i 1;i len;i) {for(auto u : vec[i]) vis[u] 1;while(!lQ.empty() vis[lQ.top()]) lQ.pop();lft[i] 1;if(lQ.empty()) {lQ.push(i);vec[i np[i]].push_back(i);continue;}else {lft[i] std::max(lft[i],(i-lQ.top()1)/2*2(lQ.top()%20));}lQ.push(i);vec[i np[i]].push_back(i);}for(int i 0;i (N 1);i) vec[i].clear();memset(vis,0,sizeof(vis)); std::priority_queueint gQ;for(int i len-1;i;--i) {for(auto u : vec[i]) vis[u] 1;while(!gQ.empty() vis[gQ.top()]) gQ.pop();rgt[i] 1;if(gQ.empty()) {gQ.push(i);vec[i - np[i]].push_back(i);continue;}else {rgt[i] std::max(rgt[i],(gQ.top()-i1)/2*2(gQ.top()%20));}gQ.push(i);vec[i - np[i]].push_back(i);}int ans 0;for(int i 1;i2 len;i) if(i%20)ans std::max(ans,lft[i]rgt[i2]);return ans;
}int main() {std::cin s;std::cout Manacher() std::endl;return 0;
}
