【模板】manacher算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【模板】manacher算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1629字，纯文字阅读大概需要3分钟。

内容图文

看进阶指南的时候看到的算法,正好最近没啥事干来学一下

大致题意

给一个长度为\(n\)字符串\(S\),求\(S\)中的最长回文字串

\(n≤1.1×10^7\)

---

分析

算法一

暴力

枚举每个点能扩散到的最大长度

时间复杂度\(O(n^2)\)

---

算法二

\(hash+\)二分

建立出\(S\)的前后缀\(hash\)值,然后二分答案,找到最大扩展长度

时间复杂度\(O(nlogn)\)

---

算法三

\(manacher\)麻辣串算法

算法流程

1.在每两个字符间插入一个额外字符,以去掉偶回文串的情况

---

2.定义\(r_i\)表示以\(i\)为中心时的最大回文半径

\(R\)表示当前情况能扩展到的最右字符\((即最右回文右端点)\)

\(mid\)表示最右回文的中心

考虑每个新进来的字符的情况:

\(1.\) \(i∈[mid,R]\)

显然,\(i\)有一个关于\(mid\)的对称点\(j = mid×2-i\)

根据对称性,\(j\)周围的字符和\(i\)周围的字符一定相同,于是可以先用\(r_j\)去更新\(r_i\)

即\(r_i = min(r_{mid×2-i},r_{mid}-i+mid)\)

(右侧不能大于\(R\),否则处于未知的位置,无法保证正确性)

最后再去试试\(i\)还能不能扩展,同时更新\(R\)和\(mid\)的值

\(2.\) \(i∈(R,n]\)

此时\(i\)处于一个未知的位置,因此只能暴力扩展,同时更新\(R\)和\(mid\)的值

最后的答案即为\((2*max(r_i)-2)/2 = max(r_i)-1\)

由于\(R\)最多会向右移\(n\)次,因此总时间复杂度为线性(\(O(n)\))

\(code\)

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 91000000;
char c[MAXN];
char s[MAXN];
int L[MAXN],R[MAXN]; 
int MAX_R;
int r[MAXN],len,mid; 
void manacher(){
	for(int i=1;i<len;i++){
		if(MAX_R>i&&mid<=i) r[i] = min(r[mid*2-i],r[mid]-i+mid);
		else r[i] = 1;
		while(s[i+r[i]]==s[i-r[i]]) r[i]++;
		if(i+r[i]>MAX_R){
			mid = i;
			MAX_R = r[i]+i;	
		}
	}
}
int main(){
	cin>>c;
	s[0] ='#',s[1] = '#';
	len = strlen(c); 
	for(int i=0;i<len;i++){
		s[i*2+2] = c[i];
		s[i*2+3] = '#';
	} 
	len = len*2+2;
	int ans = -114514;
	manacher();
	for(int i=0;i<len;i++){
		ans = max(ans,r[i]);
	}
	cout<<ans-1;
} 

内容总结

以上是互联网集市为您收集整理的【模板】manacher算法全部内容，希望文章能够帮你解决【模板】manacher算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---