湛江市手机网站建设企业,手机免费制作网站模板,海外购物网站哪个最好,全球著名科技网站Manacher(马拉车算法)
Manacher算法主要用于求解回文串问题#xff0c;能够统计出以每一个位置为中心的回文串的个数#xff0c;效率极高。
模板
题目描述
Manacher算法的实现过程#xff1a; 1.在字符串每两个字符之间插入一个分隔符。 2.iii从111到nnn求解P[i]P[i]P[i…Manacher(马拉车算法)
Manacher算法主要用于求解回文串问题能够统计出以每一个位置为中心的回文串的个数效率极高。
模板
题目描述
Manacher算法的实现过程 1.在字符串每两个字符之间插入一个分隔符。 2.iii从111到nnn求解P[i]P[i]P[i]表示以iii为中心的最长回文子串长度同时记录一个当前延伸最远的回文子串记它的右端点为rightrightright中心点为midmidmid则求P[i]P[i]P[i]时若rightirightirighti那么P[i]的长度至少为min(right−i,P[mid−(i−mid)])P[i]的长度至少为min(right-i,P[mid-(i-mid)])P[i]的长度至少为min(right−i,P[mid−(i−mid)])然后再暴力地向两边拓展即可。
时间复杂度为均摊O(n)O(n)O(n)。
// luogu-judger-enable-o2
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN20000005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
char st[MAXN],s[MAXN];
int P[MAXN];
int main()
{scanf(%s,st);int lenststrlen(st);s[0]%,s[1]#;for (int i0;ilenst;i) s[i*22]st[i],s[i*23]#;int lenslenst*21;int mid0,right0;int smax0;for (int i1;ilens;i){P[i](righti?min(P[mid*2-i],right-i):1);while (s[i-P[i]]s[iP[i]]) P[i];if (rightiP[i]) rightiP[i],midi;smaxmax(smax,P[i]);}printf(%d\n,smax-1);return 0;
}一道例题
CF30E. Tricky and Clever Password
Solution
其实这并不是一道Manacher题只是需要一步Manachcer预处理。
我们发现最后一个串suffixsuffixsuffix一定是原串的一个后缀因此我们考虑枚举suffixsuffixsuffix的长度找到最前面的一个prefixprefixprefix使得prefixprefixprefix是suffixsuffixsuffix的反串这一部分可以用KMP实现。
在找到prefix,suffixprefix,suffixprefix,suffix以后我们还需要找一个最优的middlemiddlemiddle它是一个长度为奇数的回文串并包含在[preffix1,suffix−1][preffix1,suffix-1][preffix1,suffix−1]之间但我们直接求这里面的最长回文子串是不行的因为其中的最长回文子串可能会与preffixpreffixpreffix或suffixsuffixsuffix重合因此考虑二分答案则问题变成了判断[preffix1mid,suffix−1−mid][preffix1mid,suffix-1-mid][preffix1mid,suffix−1−mid]之间是否有最长回文子串长度大于midmidmid。
这就变成了一个区间最长回文子串最大值Manacher求出P[i]P[i]P[i]之后STSTST表预处理就能够O(1)O(1)O(1)询问了。
总时间复杂度为O(nlgn)O(nlgn)O(nlgn)。
个人实现比较丑陋。。。
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods998244353;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
struct Ansnode{ int l,mid,len,c; } Ans;
char s[MAXN],t[MAXN],St[MAXN];
PR mx[MAXN][20];
int Log[MAXN],nxt[MAXN],P[MAXN];
void InitKMP(char *st,int len)
{for (int i2,j0;ilen;i){while (jst[i]!st[j1]) jnxt[j];if (st[i]st[j1]) j;nxt[i]j;
// coutNxt:i nxt[i]endl;}
}
void Manacher(char *st,int len)
{St[0]%,St[1]#;for (int i1;ilen;i) St[i1]st[i],St[i1|1]#;
// coutStendl;int Lenlen1|1,mid0,right0;for (int i1;iLen;i){P[i](righti?min(P[mid*2-i],right-i):1);while (St[i-P[i]]St[iP[i]]) P[i];
// couti P[i]endl;if (rightiP[i]) rightiP[i],midi;}for (int i1;ilen;i) {if (P[i*2]-1Ans.c) Ans(Ansnode){0,i,0,P[i*2]-1};P[i]P[i*2]1;
// coutP[i]endl;}
}
PR max(PR x,PR y){ return x.fiy.fi?x:y; }
void InitST(int n)
{Log[1]0;for (int i2;in;i) Log[i]Log[i1]1;for (int i1;in;i) mx[i][0]MP(P[i],i);for (int i1;iLog[n];i)for (int j1;jn-(1i)1;j) mx[j][i]max(mx[j][i-1],mx[j(1(i-1))][i-1]);
}
PR querymx(int l,int r)
{if (lr) return MP(-100000,0);int tLog[r-l1];return max(mx[l][t],mx[r-(1t)1][t]);
}
PR getans(int L,int R)
{if (LR) return MP(-100000,0);int l1,r(R-L)/21;while (lr){int mid(lr1)1;if (querymx(Lmid-1,R-mid1).fimid) lmid;else rmid-1;}return MP(l,querymx(Ll-1,R-l1).se);
}
int main()
{scanf(%s,t1);int lenstrlen(t1);for (int i1;ilen;i) s[i]t[len-i1];InitKMP(s,len);Manacher(t,len);InitST(len);int ans0;for (int l1,i1,j0;llen;l){
// coutl i j t[i1] s[j1]endl;for (;ilen;i){while (jt[i]!s[j1]) jnxt[j];if (t[i]s[j1]) j;if (jl){PR qgetans(i1,len-l);
// couti1 len-l j:q.fi q.seendl;if (q.fiq.fill-1Ans.c) Ans(Ansnode){i-l1,q.se,l,q.fiq.fill-1};i;break;}}}if (!Ans.len) { puts(1); printf(%d %d\n,Ans.mid-(Ans.c-1)/2,Ans.c); }else { puts(3); int qAns.c-Ans.len*2;printf(%d %d\n,Ans.l,Ans.len);printf(%d %d\n,Ans.mid-(q-1)/2,q);printf(%d %d\n,len-Ans.len1,Ans.len);}return 0;
}
/*
xjowabclwjegohghlewcba
*/
