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

2023-09-05 18:12:05 172

回文

利用python自带的翻转函数reversed()

defis_plalindrome(string):returnstring==''.join(list(reversed(string)))`

自己实现

defis_plalindrome(string):
string=list(string)
length=len(string)
left=0
right=length-1
whileleft


最长的回文子串
暴力破解
暴力破解，枚举所有的子串，对每个子串判断是否为回文，时间复杂度为O(n^3)
动态规划
defsolution(s):
s=list(s)
l=len(s)
dp=[[0]*lforiinrange(l)]
foriinrange(l):
dp[i][i]=True
#当k=2时要用到
dp[i][i-1]=True
resLeft=0
resRight=0
#枚举子串的长度
forkinrange(2,l+1):
#子串的起始位置
foriinrange(0,l-k+1):
j=i+k-1
ifs[i]==s[j]anddp[i+1][j-1]:
dp[i][j]=True
#保存最长的回文起点和终点
ifresRight-resLeft+1
时间复杂度为O(n^2),空间复杂度为O(n^2)
Manacher算法
Manacher算法首先对字符串做一个预处理,使得所有的串都是奇数长度,插入的是同样的符号且符号不存在与原串中，串的回文性不受影响
aba=>#a#b#a#abab=>#a#b#a#b#`


我们把回文串中最右位置与其对称轴的距离称为回文半径，Manacher算法定义了一个回文半径数组RL，RL[i]表示以第i个字符为对称轴的回文半径，对于上面得到的插入分隔符的串来说，我们可以得到RL数组
char:#a#b#a#
RL:1214121
RL-1:0103010
i:0123456
char:#a#b#a#b#
RL:121414121
RL-1:010303010
i:012345678


我们还求了RL[i]-1:我们发现RL[i]-1正好是初始字符串中以位置i为对称轴的最长回文长度
所以下面就是重点如何求得RL数组了，可以参考这篇文章(讲得比较清晰)
下面是算法实现
defmanacher(preS):
s='#'+'#'.join(preS)+'#'
l=len(s)
RL=[0]*l
maxRight=pos=maxLen=0
foriinrange(l):
ifi=0andi+RL[i]maxRight:
maxRight=i+RL[i]-1
pos=i
maxLen=max(RL)
idx=RL.index(maxLen)
sub=s[idx-maxLen+1:idx+maxLen]
returnsub.replace('#','')


空间复杂度：借助了一个辅助数组，空间复杂度为O(n)
时间复杂度：尽管内层存在循环，但是内层循环只对尚未匹配的部分进行，对于每一个字符来说，只会进行一次，所以时间复杂度是O(n)
最长回文前缀
所谓前缀，就是以第一个字符开始
下面的最长回文前缀
abbabbc=>abbc
abababb=>ababa
sogou=>s

将原串逆转，那么问题就转变为求原串的前缀和逆串后缀相等且长度最大的值,这个问题其实就是KMP算法中的next数组的求解了
具体求解：将原串逆转并拼接到原串中，以'#'分隔原串和逆转避免内部字符串干扰。
deflongest_palindrome_prefix(s):
ifnots:
return0
s=s+'#'+s[::-1]+'$'
i=0
j=-1
nt=[0]*len(s)
nt[0]=-1
whilei


添加字符生成最短回文字符串
这道题其实跟上面基本是一样的，
实例：
aacecaaa->aaacecaaa#添加a
abcd->dcbabcd#添加dcb


我们先求字符串的最长回文前缀,然后剩余的字符串逆转并拼接到字符串的头部即是问题所求
defsolution(s):
length=longest_palindrome_prefix(s)
returns[length:][::-1]+s


最长回文子序列
动态规划法

dp[i][j]表示子序列s[i..j]中存在的最长回文子序列长度
初始化dp[i][i]=1
当s[i]==s[j]为true时，dp[i][j]=dp[i+1][j-1]+2
当s[i]==s[j]为false时，dp[i][j]=max(dp[i+1][j],dp[i][j-1])



#求得最长回文子序列的长度
defsolution(s):
l=len(s)
dp=[[0]*lforiinrange(l)]
foriinrange(l):
dp[i][i]=1
#枚举子串的长度
forkinrange(2,l+1):
#枚举子串的起始位置
foriinrange(0,l-k+1):
j=i+k-1
ifs[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])
returndp[0][l-1]
时间复杂度为O(n^2),空间复杂度为O(n^2)
总结
以上所述是小编给大家介绍的Python实现常见的回文字符串算法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

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

热门推荐

随机推荐