Manacher

1.暴力

找出所有子串，遍历每个子串判断它们是否为回文串

复杂度：

O(n^2)

2.manacher

p[i]：第i个节点的回文半径方法：加入没有的字符，如 # 等。用p[i]表示第i个节点回文的半径。

最大的

p[i] - 1

就是答案。

从数值上看，插入玩字符后，回文串长度为原串长度 * 2 + 1.等于这个回文串长度 * 2 + 1相等

于是就转换成如何快速求出p数组

利用回文串对称性扩展回文串，p[i]不在直接赋值为1，而是根据之前求出的p[j]，

0 < j < i

用mx表示所有字串产生的最大回文子串的最大右边界，Id表示产生这个最大右边界的对称轴的位置。

So?

实现

分类讨论

情况 1 $i < mx$ 利用回文串性质，对于i,可以找到一个关于id对称的位置 j = id * 2 - i，惊醒加速查找。而次情况有分为三种情况。
- 1.1
此时o[i] = p[j] 此时，串i可以再向两边扩张，如果可以向两边扩张，p[j]也可以，而p[j]已经确定了，所以串i不想两边扩张。
- 1.2
此时p[i] = p[j] 但是串i可以再向两边扩张。一看就知道。~~但是看不到~~

-1.3

此时p[i] = mx - i 此时只确定i在mx以内的部分回文，并不能确定串i和串j相同。所以不能往外扩张.
情况2 i >= mx

之前记录的用不上了，所以p[i] = 1;

模版：

CPP

int init(){//初始化 
	int len = strlen(s);
	str[0] = '@';
	str[1] = '#';//@防止数组越界，#添加字符
	int j = 2;
	for(int i = 0; i < len; i ++){
		str[j ++] = s[i];
		str[j ++] = '#';
	}
	str[j] = '\0';
	return j;
}

int manacher(){
	int ans = -1, len = init(), mx = 0, id = 0;//mx为右边界
	for(int i = 1 ; i < len; i ++){
		if(i < mx)
			p[i] = min(p[id * 2 - i], mx - i);
		else
			p[i] = 1;
		while(str[i + p[i]] == str[i - p[i]])
			p[i] ++;
		if(p[i] + i > mx){
			mx = p[i] + i;
			id = i;
		}
		ans = max(ans, p[i] - 1);
	}
	return ans;
}

Manacher

文章操作

manacher

相关定义：回文字符串

1.暴力

2.manacher

实现

模版：

相关推荐

评论

Manacher