首页 > 其他分享 >Manacher

Manacher

时间:2024-02-14 22:00:23浏览次数:22  
标签:int Manacher mx 枚举 1b id 回文

Manacher

是找出字符串中回文子串很有效的算法

具体而言,是在暴力的基础上一步步优化

首先,最暴力的是 \(O(n^2)\) 枚举左右端点,再 \(O(n)\) 判断

但可以直接枚举中间点,优化到 \(O(n^2)\)

此时出现了个问题:长度为奇数的回文串中点在中间字母,

但长度为偶数的回文串中间点在空隙处!

所以,我们把空隙处插入'#'的特殊字符(保证与其它字符不同),就更方便枚举空隙(在最前面和最后面也加入)

但 $O(n^2) $的复杂度也不理想

# a # b # b # a # a # b # b #

这时我们要利用回文串本身的对称性

看第3个#号,易知以它为中心,两段字符对称最长可延伸至开头和第5个#(\(mx\),此时已找出的回文串最大的右边界)处(也就是最长回文子串)

向后移一个看b(记作 \(p[2b]\)),此时以第3个 # \((id)\) 为对称点,它与第1个b完全对称,记为 \(p[1b]\),\(p[i]\) 中存了以 \(i\) 为对称中心的极长回文串长度 \(+1\) 的值

那么当 \(1b<=mx\) 时,

  1. 若 \(id\times 2-mx\)(\(mx\) 关于 \(id\) 对称点)\(>1b-p[1b]\),即以 \(1b\) 为中心点回文子串超出 \(mx\) 范围,则\(p[2b]\) 初始为 \(mx-2b\),剩下只能暴力枚举

  2. 若 \(id\times 2-mx\le 1b-p[1b]\),则以 \(1b\) 为中心点回文子串与以 \(2b\) 为中心点回文子串一模一样(对称),即 \(p[2b]=p[1b]\)

当 \(1b>mx\) 时,只能枚举了

分析:

时间复杂度:\(O(n)\)

循环好理解,但暴力查询为何线性?

因为假如 \(i+p[i]\) 比 \(mx\) 小,根本不会执行 \(while\) ,不用枚举

但即便 \(i+p[i]\) 比 \(mx\) 大,由于 \(mx\) 为已找出的回文串最大的右边界,因此\(mx\)递增,自然此时 \(i+p[i]\) 要比 \(mx\) 大也应递增


应用:

1. 重载比较方式

P3501 [POI2010]ANT-Antisymmetry

\(solution\):

直接把比较回文串的相等改为异或为 \(1\) 则相等即可

注意此时 #​ 为通配符

代码:

for(int i = 1; i <= n * 2; i += 2)
	{
		p[i] = (mx > i) ? min(mx - i + 1, p[id * 2 - i]) : 1;
		while(i - p[i] >= 1 && i + p[i] <= n * 2 && (t[i - p[i]] != t[i + p[i]] || (t[i - p[i]] == '#')))
			p[i]++;
		sum += p[i] >> 1;
		if(i + p[i] - 1 > mx)   mx = i + p[i] - 1, id = i;
	}

2. 找所有回文串(个数等)

P1659 [国家集训队]拉拉队排练

\(solution\):

题目只让我们求串长为奇数的串,且要找前 \(k\) 大的串长之积

比较显然的想法是开数组 \(tong\) 对每个长度记录个数,但个数太多直接算不行

注意 \(manacher\) 求的是极长回文子串,也就是一个长为 \(x\) 的包含长为 \(x-2,x-4\cdots\) 的回文串

那除去下标为偶数位的,相当于覆盖了数组的前缀

因此,从大到小枚举奇数位到位置 \(x\),\(sum\) 为 \(tong[x+2\sim n]\) 的和,那长为 \(x\) 的回文串个数为 \(tong[x]+sum\)

或者相当于极长长度为 \(x\) 的串把 \(tong[1\sim x]+1\),用差分维护

代码:

	for(int i = 1; i <= n * 2 + 1; i++)
	{
		p[i] = (mx > i) ? min(p[id * 2 - i], mx - i) : 1;
		while(t[i - p[i]] == t[i + p[i]])	p[i]++;
		if(i + p[i] > mx)	mx = i + p[i], id = i;
		if(i % 2 == 0)	tong[1]++, tong[p[i] / 2 + 1]--;
	}
	for(int i = 1; i <= (n + 1) / 2 + 1; i++)	
	{
		tong[i] += tong[i - 1];
		sum += tong[i];
		if(tong[i])	maxx = max(maxx, (ll)i);
	}
	if(sum < k)	printf("-1");
	else
	{
		ll noww = k;
	    for(int i = maxx; i > 0; i--)
	    {
	    	if(noww - tong[i] < 0 && noww > 0)	
	    	{
	    		ans = ans * qmi((ll)(i * 2 - 1), noww) % mod;
	    		break;
			}
			else if(noww - tong[i] < 0 && noww <= 0)	break;
	    	ll lsh = qmi((ll)(i * 2 - 1), tong[i]);
	    	if(tong[i])	ans = ans * lsh % mod; 
	    	noww -= tong[i];
		}
		printf("%lld", ans);
	}

3. 进行 dp

P4555 [国家集训队]最长双回文串

\(solution\):

注意到拼接时两个串不一定都是极长的,因此 \(manacher\) 后得额外进行 dp

因为中间没有重复字符,所以想枚举中间的端点,则端点一定为 #​

设 \(l[i]\) 表示以 \(i\) 为左端点点的极长回文串,\(r[i]\) 为以 \(i\) 为右端点的极长回文串

在 \(manacher\) 时对极长的串进行预处理,\(l[i-p[i]+1]=r[i+p[i]-1]=p[i]-1\)

然后每向右移两位 \(l[i]-2\),每向左移两位 \(r[i]-2\)

代码:

for(int i = 1; i <= n * 2; i++)
	{
		p[i] = (mx > i) ? min(p[id * 2 - i], mx - i) : 1;
		while(t[i - p[i]] == t[i + p[i]])	p[i]++;
		if(i + p[i] > mx)	mx = i + p[i], id = i;
		l[i - p[i] + 1] = max(l[i - p[i] + 1], p[i] - 1);
		r[i + p[i] - 1] = max(r[i + p[i] - 1], p[i] - 1);
	}
	for(int i = 1; i <= n * 2; i += 2)	l[i] = max(l[i], l[i - 2] - 2);
	for(int i = n * 2; i > 0; i -= 2)	r[i] = max(r[i], r[i + 2] - 2);
	for(int i = 1; i <= n * 2; i += 2)	
	    if(r[i] && l[i])	ans = max(ans, l[i] + r[i]);

4. P6216 回文匹配

先求出那些左端点后面可以接上 \(s_2\),做前缀和

对 \(s_1\) 跑 manacher

对于一个回文中心有极长回文串 \([l,r]\),那么 \([l,r-len+1]\) 中的左端点就能产生贡献

前缀和相减就是 \(qzh_{r-len+1}-qzh_{l-1}\)

但是还有 \([l+1,r-1],[l+2,r-2]\dots\),也需要计算

\(qzh_{r-len+1}-qzh_{l-1}+qzh_{r-len}-qzh_{l-2}\dots\)

发现加的前缀和是一个区间,减的前缀和也是一个区间

再次前缀和,注意边界的计算

int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> m >> (s + 1) >> (t + 1);
	lens = strlen(s + 1), lent = strlen(t + 1);
	s[0] = '~', s[lens + 1] = '#', pw[0] = 1; 
	for(ui i = 1; i <= lens; ++i)	
		hsh[i] = hsh[i - 1] * P + s[i], pw[i] = pw[i - 1] * P;
	for(ui i = 1; i <= lent; ++i)	hah = hah * P + t[i];
	for(ui i = 1; i + lent - 1 <= lens; ++i)
		if(gethsh(i, i + lent - 1) == hah)	++num[i];
	for(ui i = 1; i <= lens; ++i)	tot[i] = tot[i - 1] + num[i];
	for(ui i = 1; i <= lens; ++i)	sum[i] = sum[i - 1] + tot[i];
	for(ui i = 1; i <= lens; ++i)
	{
		p[i] = (mx > i) ? min(p[id * 2 - i], mx - i) : 1;
		while(s[i - p[i]] == s[i + p[i]])	++p[i];
		if(i + p[i] > mx)	mx = i + p[i], id = i;
		if(i + p[i] - 1 - (i - p[i] + 1) + 1 < lent || i <= lent / 2)	continue;
		ui r = i + (lent / 2), l = i - (lent / 2);
		if(i - p[i])	ans += sum[i + p[i] - lent] - sum[r - lent] - (sum[l - 1] - sum[i - p[i] - 1]);
		else	ans += sum[i + p[i] - lent] - sum[r - lent] - (sum[l - 1] - sum[i - p[i]]);
	}
	cout << ans;
	return 0;
}

5. 在扩展时计算答案

P4287 [SHOI2011] 双倍回文

首先应枚举中间的断点,因为整个串也是回文串,在这个串中找答案

关键在快速枚举左右的中心

在 \(mx\) 被更新时,可以枚举串的右端点,则中间和右端点的中点则是右半部分的中心

关于中间对称的位置应该是左半部分的中心,判断它是否满足条件

Q1:为什么这样不会漏掉答案呢?

因为如果没发生拓展,则在另一边对称的有完全相同的回文串,没必要枚举了

Q2:为什么时间复杂度是 \(O(n)\)?

因为枚举端点是 \(mx\sim i+p_i\),而下一轮 \(mx\) 即更新为 \(i+p_i\),原理同 manacher 复杂度分析

所以,一个串中有多少个本质不同的回文串?

\(O(n)\) 个!

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010, inf = 1e9;
int n, p[N], id, mx, ans, q[N], hh = 1, tt, tree[N << 2];
char t[N], s[N];
int main()
{
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> (t + 1);
	s[0] = '~', s[n * 2 + 1] = '#', s[n * 2 + 2] = '$';
	for(int i = 1; i <= n; ++i)	s[i * 2] = t[i], s[i * 2 - 1] = '#';
	for(int i = 1; i <= n * 2; ++i)
	{
		p[i] = (mx > i) ? min(p[id * 2 - i], mx - i) : 1;
		while(s[i - p[i]] == s[i + p[i]])	++p[i];
		if(i + p[i] > mx)	
		{
			if(i & 1)
				for(int j = max(i + 4, mx); j < i + p[i]; ++j)
					if((j - i) % 4 == 0 && p[i * 2 - (i + j) / 2] + i * 2 - (i + j) / 2 >= i)	
						ans = max(ans, j - i);
			mx = i + p[i], id = i;
		}
	}
	cout << ans;
	return 0;
}

6. P5446 [THUPC2018] 绿绿和串串

发现复制的本质是把串变成以末尾字符为中心的回文串

然后原串一定是 \(S\) 的前缀

对 \(S\) 跑 manacher

如果只复制一次,那么可以通过判断以当前点为中心回文的部分能否覆盖到末尾判断

复制多次看起来有点麻烦

但如果复制一次,得到的串可以再经过一系列复制得到 \(S\),就判断这个结尾可以

倒着处理,类似 DP 的思想

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> T;
	while(T--)
	{
		cin >> s, n = s.length();
		t.clear();	t.pb('~'), t += s;
		t.pb('$'), mx = id = las = 0;
		for(int i = 1; i <= n; ++i)
		{
			book[i] = 0, p[i] = (mx > i) ? min(p[id * 2 - i], mx - i) : 1;
			while(t[i - p[i]] == t[i + p[i]])	++p[i];
			if(i + p[i] > mx)	mx = i + p[i], id = i; 
		}
		for(int i = n; i > n / 2; --i)
			if(i + p[i] - 1 >= n)	book[i] = 1, las = i;
		for(int i = n / 2; i > 0; --i)
			if(i == p[i])
			{
				if(book[i + p[i] - 1])	las = i, book[i] = 1;
			}
		for(int i = 1; i <= n; ++i)
			if(book[i])	print(i), putchar(' ');
		putchar('\n');
	}
	return 0;
}

标签:int,Manacher,mx,枚举,1b,id,回文
From: https://www.cnblogs.com/KellyWLJ/p/18015663

相关文章

  • Manacher
    ManacherManacher(马拉车)能在O(n)的时间复杂度内求出字符串中以字符i为中心的最长回文半径r[i]算法流程预处理为了避免奇偶性问题在字符串开始加上奇怪的@在字符串末尾加上&在字符中间加上#本段代码来自可爱的w++并且把他老婆inline删掉了voidInit(){scanf("%......
  • manacher
    记录23:392024-2-5manacher算法,是可以在O(n)时间计算回文串的算法具体思路可以查看Manacher非常有意思的算法。利用了俩个数组d1[i]和d2[i]分别来记录以位置i为中心的长度为奇数和长度为偶数的回文串个数这里利用了回文串个数也即以i为中心的最长回文串的半径长度(半......
  • manacher 学习笔记
    定义与基本求法定义又名马拉车,用于处理子串回文问题。基本求法暴力判断每个子串是否是回文是\(O(n^3)\)的,根据其对称性优化为\(O(n^2)\)依旧是不优秀的。马拉车便是解决这种单一问题的算法,具有局限性,但同时是解决这种问题的不二选择。枚举回文串的中点,例如\(aaba......
  • 最小表示法&Manacher学习笔记+杂题
    字符串系列前言:孩子从小就自卑。四、最小表示法&Manacher学习笔记+杂题相关题单:戳我1.最小表示法最小表示法是用于解决字符串最小表示问题的方法。(1)字符串的最小表示:字符串\(s\)的最小表示为与\(s\)循环同构的所有字符串中字典序最小的字符串。循环同构指的是当字符......
  • 最小表示法&Manacher学习笔记+杂题
    字符串系列前言:孩子从小就自卑。四、最小表示法&Manacher学习笔记+杂题相关题单:戳我1.最小表示法最小表示法是用于解决字符串最小表示问题的方法。(1)字符串的最小表示:字符串\(s\)的最小表示为与\(s\)循环同构的所有字符串中字典序最小的字符串。循环同构指的是当字符......
  • 【学习笔记】manacher
    众所周知,manacher又叫“马拉车”算法,是一种线性求解最长回文子串的算法。推荐结合模板阅读此文。求最长回文子串,首先想到的是暴力。枚举子串的左右端点\(l,r\),再判断这个子串是否回文。总复杂度\(O(n^3)\),效率过低。观察发现,我们可以只枚举中点,然后同时向左右不断扩展,当无......
  • 高铁拉我,马拉车——记高铁路上的manacher
    目录前言问题引入思路一览manacher高效的原因具体情况讨论小问题的讨论code前言不得为什么,总会在奇奇怪怪的时候特定时间看算法比平常看得舒服多了,之前看字符串匹配的时候自然是准备把马拉车一起看了的,但是那时候看不下去,昨天回家的高铁上再次看了看,觉得格外的亲切,emmm问题引入......
  • 【CF30E】Tricky and Clever Password 题解(manacher + exKMP)
    manacher+exKMP+二分。感觉是最粗暴的方法,想出来之后自己硬莽了4k,荣获题解区最长。Solution约定:下文所提及到的所有的回文串,均指奇长度回文串。显然把题目拆成两个部分,中间的回文串,以及两边相同的连续子串。考虑一下从哪个入手比较好。忘记是咋想的了,易得从两边相同......
  • Manacher与exKMP(扩展KMP,Z函数)
    Manacher算法该算法由GlennK.Manacher在1975年提出,首先注意到回文串的对称中心特性可能有所不同(中心可能为一个字符或者是在两个字符之间),那么我们将字母之间插入隔板,这两个回文串的对称中心就都在一个字符上了,suchas"|A|B|B|A|"、"|A|B|C|B|A|"过程对于一个回文串,有且......
  • KMP算法和Manacher算法
    KMP算法KMP算法解决的问题KMP算法用来解决字符串匹配问题:找到长串中短串出现的位置.KMP算法思路暴力比较与KMP的区别暴力匹配:对长串的每个位,都从头开始匹配短串的所有位.KMP算法:将短字符串前后相同的部分存储在\(next\)数组里,让之前匹配过的信息指导之后的匹配.......