# Python实现常见的回文字符串算法

## 回文

def is_plalindrome(string):
return string == ''.join(list(reversed(string)))

def is_plalindrome(string):
string = list(string)
length = len(string)
left = 0
right = length - 1
while left < right:
if string[left] != string[right]:
return False
left += 1
right -= 1
return True

## 动态规划

def solution(s):
s = list(s)
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = True
# 当 k = 2时要用到
dp[i][i - 1] = True
resLeft = 0
resRight = 0
# 枚举子串的长度
for k in range(2, l+1):
# 子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
# 保存最长的回文起点和终点
if resRight - resLeft + 1 < k:
resLeft = i
resRight = j
return ''.join(s[resLeft:resRight+1])

## Manacher 算法

Manacher 算法首先对字符串做一个预处理,使得所有的串都是奇数长度, 插入的是同样的符号且符号不存在与原串中，串的回文性不受影响

aba => #a#b#a#
abab => #a#b#a#b#

char:  # a # b # a #
RL:    1 2 1 4 1 2 1
RL-1:  0 1 0 3 0 1 0
i:     0 1 2 3 4 5 6
char: # a # b # a # b #
RL:   1 2 1 4 1 4 1 2 1
RL-1: 0 1 0 3 0 3 0 1 0
i:    0 1 2 3 4 5 6 7 8

def manacher(preS):
s = '#' + '#'.join(preS) + '#'
l = len(s)
RL = [0] * l
maxRight = pos = maxLen = 0
for i in range(l):
if i < maxRight:
RL[i] = min(RL[2*pos - i], maxRight-i)
else:
RL[i] = 1
while i - RL[i] >= 0 and i + RL[i] < l and s[i - RL[i]] == s[i + RL[i]]:
RL[i] += 1
if i + RL[i] - 1 > maxRight:
maxRight = i + RL[i] - 1
pos = i
maxLen = max(RL)
idx = RL.index(maxLen)
sub = s[idx - maxLen + 1: idx + maxLen]
return sub.replace('#', '')

## 最长回文前缀

abbabbc => abbc
abababb => ababa
sogou => s

def longest_palindrome_prefix(s):
if not s:
return 0
s = s + '#' + s[::-1] + '\$'
i = 0
j = -1
nt = [0] * len(s)
nt[0] = -1
while i < len(s) - 1:
if j == -1 or s[i] == s[j]:
i += 1
j += 1
nt[i] = j
else:
j = nt[j]
return nt[len(s) - 1]

## 添加字符生成最短回文字符串

aacecaaa -> aaacecaaa # 添加 a
abcd -> dcbabcd # 添加 dcb

def solution(s):
length = longest_palindrome_prefix(s)
return s[length:][::-1] + s

## 动态规划法

1. dp[i][j] 表示子序列 s[i..j] 中存在的最长回文子序列长度
2. 初始化dp[i][i] = 1
3. 当 s[i] == s[j] 为 true 时，dp[i][j] = dp[i+1][j - 1] + 2
4. 当 s[i] == s[j] 为 false 时，dp[i][j] = max(dp[i+1][j], dp[i][j - 1])
# 求得最长回文子序列的长度
def solution(s):
l = len(s)
dp = [[0] * l for i in range(l)]
for i in range(l):
dp[i][i] = 1
# 枚举子串的长度
for k in range(2, l+1):
# 枚举子串的起始位置
for i in range(0, l-k+1):
j = i + k - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j - 1] + 2
else:
dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
return dp[0][l-1]

0 条评论

• ### Chrome断点JS寻找淘宝签名sign

写了这篇文章淘宝sign加密算法 之后，很多人问我Chrome断点调试怎么做，今天会尽量详细聊聊。如果你用使用过Pycharm的断点，会更好理解。

• ### 敲敲级简单的鉴别H图片的小程序

首先，来看一下程序运行结果的截图 ? 功能实现 一、下载SDK pip install qcloud_image 先贴出官方给的实例代码： #!/usr/bi...

• ### LeetCode 188. 买卖股票的最佳时机 IV（动态规划）

这道题需要考虑一个 k 非常大的时候，k > n/2 时，就可以看做股票第2题了，无限次数。最多可以交易 min(k, n/2) 次

• ### 【黎乙丙】教你在3分钟安装ps笔刷

Photoshop笔刷可以打开一个全新的创意世界。画笔可让您以任何可想象的方式绘画和绘画 - 从简单的纹理到任何可想象的元素中的图案（从简单的叶子到美丽的夜空）...

• ### 从网络上下载省份城市名称并存入文件然后进行读取省份城市

//实现的功能是 从后台拿到城市的省份以及名称，然后保存在本地的沙盒中 在使用的时候再拿出来用。 步骤1 //向后台请求数据 //忽略缓存 [Requ...

这个flag告诉链接器把库中定义的Objective-C类和Category都加载进来。这样编译之后的app会变大（因为加载了其他的objc代码进来）。但是如果...

• ### 微服务的最终一致性与事件流

微服务是指一个个单个小型业务功能的服务，由于各个微服务开发部署都是独立的，因此微服务天然是分布式的，因此，分布式系统的设计问题如CAP定理同样适合微服务架构，虽...

• ### 跟我学Spring Cloud（Finchley版）-22-Spring Cloud Config-配置动态刷新

这样，修改 profile 配置后，只需向应用的 /actuator/refresh 端点发送POST请求，即可刷新该属性。例如：