最长的回文子串
5星
- 浏览量: 0
- 大小:None
- 文件类型：PDF
简介：
《最长的回文子串》是一道经典的计算机算法题目，要求在给定字符串中找到长度最长且正反读相同的子串，挑战编程者优化算法以高效解决问题。
最长回文子串
给定一个字符串str，返回str中最长回文子串的长度。
举例：
- str=123，其中的最长回文子串为”1″、“2″或者”3”，所以返回1。
- str=abc1234321ab，其中的最长回文子串为”1234321″，所以返回7。
暴力遍历法
以每个字符为中心向外扩展检查其左右两边是否相同。最坏情况下每次扩至字符串两端，因此时间复杂度为O(N²)，N是字符串长度。
注意：
- 回文串是指正读反读都能保持相同的字符串，如“madam”或“121”。
最长回文子串问题可以通过多种算法解决，其中暴力遍历法是最简单但效率较低的方法。该方法以每个字符为中心向外扩展检查其左右两边的字符是否相等，从而判断这个字符是否属于一个回文子串。对于每个字符都需要进行两次遍历来找到可能的最长回文子串，因此时间复杂度为O(N²)。
为了提高效率可以采用Manacher算法（也称为马拉车算法）。该算法利用了回文串的对称性来减少重复计算。首先构建一个辅助字符串，在原字符串中的每个字符间插入特殊字符（例如#），这样可以让每个回文子串的中心在辅助字符串中显式存在。然后，维护一个回文半径的最大值p_r和对应的中心索引index，遍历过程中如果当前位置i不在当前回文子串的对称范围内就尝试向两边扩展；若在范围之内就可以利用对称性快速更新回文半径。这样Manacher算法的时间复杂度降低到O(N)，大大提高了效率。
以下是暴力遍历和Manacher算法的Python代码实现：
```python
# 暴力遍历最长回文子串
def solution(s):
max_len = 0
for i in range(len(s)):
count = 1
j = 1
while i - j >= 0 and i + j < len(s):
if s[i - j] != s[i + j]:
break
count += 2
j += 1
max_len = max(max_len, count)
return max_len
# Manacher算法
def get_manacher_str(s):
char_arr = [# + c for c in s + # + .join(list(reversed(s)))]
return .join(char_arr)
def get_long_pal_sub_str_len(s):
manacher_str = get_manacher_str(s)
pal_arr = [0] * len(manacher_str)
index = -1
p_r = -1
max_len = 0
for i in range(len(manacher_str)):
if i < p_r:
pal_arr[i] = min(pal_arr[2 * index - i], p_r - i)
else:
pal_arr[i] = 1
while i - pal_arr[i] >= 0 and i + pal_arr[i] < len(manacher_str) and manacher_str[i - pal_arr[i]] == manacher_str[i + pal_arr[i]]:
pal_arr[i] += 1
if i + pal_arr[i] > p_r:
index = i
p_r = i + pal_arr[i]
if max_len < pal_arr[i]:
max_len = pal_arr[i]
return max_len - 1
# 测试
s1 = 123
s2 = abc1234321ab
print(solution(s1)) # 输出: 1
print(solution(s2)) # 输出: 7
print(get_long_pal_sub_str_len(s1)) # 输出: 0 (因特殊字符，长度减一)
print(get_long_pal_sub_str_len(s2)) # 输出: 7
```
在实际应用中Manacher算法因其高效的性能被广泛使用。通过理解和掌握这种算法可以更好地解决与回文串相关的复杂问题，并提高程序的运行效率。
全部评论 (0)
