最长回文子串
一种方法是通过翻转字符串，然后依靠最长公共子串（而不是子序列，子序列可以用来构造回文子串）的方法来求解
Manacher 算法
- 首先通过向字符中添加 # 把原字符需要划分奇数偶数的处理变成了 统一处理
- 其次 维护 一个 P[i] 表示 以当前为中心向两边扩展的回文长度，id 当前最长的回文子串的中心， mx = id + P[id] 为字符串的边界。
- 关键思想是P[i]的更新是需要技巧的。 若 mx > i 则 P[i] >= min(P[2*id-i],mx-i) 若 mx <= i 则 P[i] = 1
- 该思想是通过
对称点来初始化 P[i] 若对称点的 回文子串包含在 目前最长串内 则初始化为与对称点一致 P[i] = P[2*id-1] 否则 对称点的回文子串超出最长子串界限，则P[i]在最长回文子串内的那段（长度mx-i）必定是回文的， 但后续情况未知，P[i] = mx-i
参考
参考代码
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> manacher(const string &str)
{
int id = 0,mx = 0;
const int len = str.length();
int P[len];
for(int i = 0; i < len; ++i)
{
P[i] = 1;
}
for(int i = 1; i < len; ++i)
{
if(mx - i > 0)
{
P[i] = min(P[2*id-i],mx-i);
}
else
{
P[i] = 1;
}
while(str[i+P[i]] == str[i-P[i]])
{
P[i]++;
}
if(P[i]+i > mx)
{
id = i;
mx = P[i]+i;
}
}
int tmp = P[0];
int index = 0;
for(int i = 0; i < len; ++i)
{
if(P[i] > tmp)
{
tmp = P[i];
index = i;
}
}
vector<int> re;
int start = index/2 - tmp/2;
int end = index/2 + (tmp-1)/2;
re.push_back(start);
re.push_back(end);
return re;
}
string preProcess(string str)
{
string reStr = "^";
int len = str.length();
for(int i = 0; i < len; ++i)
{
reStr += "#";
reStr += str[i];
}
reStr += "#$";
return reStr;
}
int main(int argc, char *argv[])
{
string str;
while(cin>>str)
{
str = "abccba";
string str1 = preProcess(str);
vector<int> tmp = manacher(str1);
for(int i = tmp[0]; i < tmp[1]; ++i)
{
cout<<str[i];
}
}
return 0;
}
|
