最长回文子串

最长回文子串

一种方法是通过翻转字符串,然后依靠最长公共子串(而不是子序列,子序列可以用来构造回文子串)的方法来求解

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

#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]++;
}
//有两种情况需要更新 一种是 找到了更长的回文子串,一种是当前的遍历下标已经超过了最长的那个回文子串的边界(开始新的一轮) 分别对应 P[i] 大 和 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;
}

T B
站点访问量: / , 本页阅读量:
T B