A-A+

字符串处理:最长回文子串,正着读,反着读都一样就是回文

2019年04月04日 算法 字符串处理:最长回文子串,正着读,反着读都一样就是回文已关闭评论 阅读 41 次

基本思路是对任意字符串,如果头和尾相同,那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同,那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。

P[i,j]P[i,j]表示第i到第j个字符的回文子串数 
dp[i,i]=1dp[i,i]=1 
dp[i,j]=dp[i+1,j−1]+2|s[i]=s[j]dp[i,j]=dp[i+1,j−1]+2|s[i]=s[j] 
dp[i,j]=max(dp[i+1,j],dp[i,j−1])|s[i]!=s[j]

python代码:

# coding: utf-8

# 字符串处理:最长回文子串,正着读,反着读都一样就是回文
# 例如:str1=baabaxyzab
# 结果:baab

def longestPalindrome(s):
    n = len(s)
    maxl = 0
    start = 0
    for i in range(n):
        if i - maxl >= 1 and s[i - maxl - 1: i + 1] == s[i - maxl - 1: i + 1][::-1]:
            start = i - maxl - 1
            maxl += 2
            continue
        if i - maxl >= 0 and s[i - maxl: i + 1] == s[i - maxl: i + 1][::-1]:
            start = i - maxl
            maxl += 1
    return s[start: start + maxl]

if __name__ == "__main__":
    str1="baabaxyzab"
    print(longestPalindrome(str1))

输出:

baab

标签:

评论已关闭!

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录