题目0x2

主要记录一些PTA解题中接触到的算法

Manacher（马拉车）（求解回文串）

参考：Manacher - OI Wiki (oi-wiki.org)

L2-008 最长对称子串（25 分）-CSDN博客

最长对称字串

image-20240413100057703

有点难理解，自己需要自己手动模拟下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<string>
using namespace std;
string s;
int p[2010];
int main()
{
	string s;
	getline(cin, s);
	int len = s.length(), id = 0, maxlen = 0;		//迄今为止找到的最右边回文串的中心。
	for (int i = len; i >= 0; --i)		//将偶回文串也转换为奇回文串
	{
		s[2 * i + 2] = s[i];
		s[2 * i + 1] = '#';
	}
	s[0] = '*';
	for (int i = 2; i < 2 * len + 1; ++i)
	{
		if (p[id] + id > i)			//检查以 id 为中心的回文串是否延伸到当前位置 i 之后。
			p[i] = p[2 * id - i] < p[id] + id - i ? p[2 * id - i] : p[id] + id - i;
        //i位于id右侧，2*id-i表示关于id对称的i，p[2 * id - i]表示回文串的半径
        //p[id] + id - i表示该回文串不延伸到右边界的最大可能半径。
        //为什么这样做呢，因为左边回文串的长度可能大于延伸到左边界的半径，而右边界外的字符串不能确定
		else
			p[i] = 1;			//否则置1，朴素算法求p[i]
		while (s[i - p[i]] == s[i + p[i]])		//朴素算法更新回文字符串的长度
			++p[i];		
		if (id + p[id] < i + p[i])		//i回文串的右边界已经超出id回文串的右边界，更新id
			id = i;
		if (maxlen < p[i])			//更新maxlen
			maxlen = p[i];


	}
	cout << maxlen - 1 << endl;			//maxlen表示以某个字符为中心的最大长度
    //如aba的回文长度为3，#a#b#a#,中maxlen为“#a#b”，4-1=3
	return 0;

}