Manacher算法
解释: 获得一个字符串的最大回文子串长度
概念:
- 回文直径: 回文字符串的长度
- 回文半径: 回文字符串长度的一半
- 回文右边界: 所有回文字符串中, 回文半径能到达的最右边的索引
- 回文右边界的中心: 第一次到达回文右边界的时候的回文中心
算法思路:
字符串预处理: 在每个字符两边都加一个标准字符. 如:ABC变成#A#B#C#. 原因: 防止偶数回文的影响
- 遍历每个字符位置, 开始向两边扩
- 如果当前位置没在回文右边界, 暴力扩(例如: 字符串ABACD, 运行到CD的位置时)
- 如果当前位置在回文右边界中, 找到当前位置关于回文中心的对称点
- 如果对称点的回文半径在C(C为回文右边界的中心)的左边(即对称点的回文直径返回内的字符都在C的回文半径中), 那么当前位置的回文半径就是这个对称点的回文半径(例如: 字符串ABCDEFGFEDCBA, 运行到FEDCBA位置时)
- 如果对称点的回文半径超过了C(即对称点的回文直径中的值存在超过回文中心点直径的范围)(例如: 字符串ABCBADABC, 运行到C位置的时候), 此时回文半径的长度是当前位置到回文右边界的长度
- 对称点的回文左边界和回文右边界中心的回文左边界相同, 此时需要从回文右边界开始向右扩
时间复杂度:
- 时间复杂度的就是回文右边界移动的范围, 所以时间复杂度为O(N)
代码:
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
| public static Tuple<int, String, int> Manacher(String str, char ch = '#')
{
if (String.IsNullOrEmpty(str))
{
return null;
}
StringBuilder sb = new StringBuilder();
sb.Append($"{ch}");
foreach (char item in str)
{
sb.Append($"{item}{ch}");
}
int[] radius = new int[sb.Length];
int moreRight = -1, center = -1;
for (int i = 0; i < radius.Length; i++)
{
if (i > moreRight)
{
int tmp = 1;
int length = 0;
while (i - tmp >= 0 && i + tmp < radius.Length && sb[i - tmp] == sb[i + tmp])
{
length++;
tmp++;
}
radius[i] = length;
center = i;
moreRight = i + tmp - 1;
}
else
{
int moreLeft = 2 * center - moreRight, symmetry = 2 * center - i;
if (symmetry - radius[symmetry] > moreLeft)
{
radius[i] = radius[symmetry];
}
else if (symmetry - radius[symmetry] < moreLeft)
{
radius[i] = moreRight - i;
}
else
{
int length = moreRight - i;
int tmp = length + 1;
while (i - tmp >= 0 && i + tmp < radius.Length && sb[i - tmp] == sb[i + tmp])
{
length++;
tmp++;
}
int newRight = i + tmp - 1;
if (newRight > moreRight)
{
moreRight = newRight;
center = i;
}
radius[i] = length;
}
}
}
int maxValue = radius[0], maxIndex = 0;
for (int i = 1; i < radius.Length; i++)
{
if (maxValue < radius[i])
{
maxValue = radius[i];
maxIndex = i;
}
}
string source = sb.ToString().Substring(maxIndex - maxValue, 2 * maxValue + 1);
StringBuilder target = new StringBuilder();
for (int i = 1; i < source.Length; i += 2)
{
target.Append($"{source[i]}");
}
return new Tuple<int, string, int>(maxValue, target.ToString(), (maxIndex - maxValue) >> 1);
}
|