# data_structure_and_algorithm -- 如何找到字符串中最长回文子串： python & java实现

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

python实现：

```def is_plalindrome(s):
s_len = len(s)
for i in range(s_len/2):
if s[i] != s[s_len-i-1]:
return False
return True

def pre_handle_string(s):
sb = '#'
s_len = len(s)
for i in range(s_len):
sb = sb + s[i] + '#'
return str(sb)

# 寻找最长回文字串
def find_longest_plalindrome_string(s):
# 预处理字符串， 加 '#'
ss = pre_handle_string(s)
# 处理后的字符长度
ss_len = len(ss)
# 右边界
right_side = 0
# 右边界对应的回文串中心
right_side_center = 0
# 保存以每个字符为中心的回文长度一半(向下取正)
half_len_arr = [0 for i in range(ss_len)]
# 记录回文中心
center = 0
# 记录最长回文长度
longest_half = 0

for i in range (ss_len):
# 是否需要中心扩展
need_calc = True
# 如果在右边界的覆盖之内
if right_side > i:
# 计算相对right_side_center的对称位置
left_center = 2*right_side_center - i
# 根据回文性质得出结论
half_len_arr[i] = half_len_arr[left_center]
# 如果超过了右边界，进行调整
if i+half_len_arr[i] > right_side:
half_len_arr[i] = right_side-i
# 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
if i+half_len_arr[left_center] < right_side:
need_calc = False
# 中心扩展
if need_calc:
while (i-1-half_len_arr[i]>=0) and (i+1+half_len_arr[i] < ss_len):
if ss[i+1+half_len_arr[i]] == ss[i-1-half_len_arr[i]]:
half_len_arr[i] = half_len_arr[i]+1
else:
break

# 更新右边界及中心
right_side = i + half_len_arr[i]
right_side_center = i
# 记录最长回文串
if half_len_arr[i] > longest_half:
center = i
longest_half = half_len_arr[i]
sb = ''
# +2是因为去掉之间添加的#
for i in range (center-longest_half+1,center+longest_half,2):
sb = sb + ss[i]

return str(sb)

if __name__ == '__main__':
test_str = ["abcdcef",
"aaaabcdefgfedcbaa",
"aaba",
"aaaaaaaaa"]
for per_str in test_str:
print ("原字串 : %s", per_str)
print ("最长回文串 : %s", find_longest_plalindrome_string(per_str))
pass```

java代码比较给力：

PlalindromeString.java

```public class PlalindromeString {

// 判断一个字符串是否回文，算法中用不到了
@Deprecated
private boolean isPlalindrome(String s) {
int len = s.length();
for(int i = 0; i < len / 2; i++) {
if(s.charAt(i) != s.charAt(len - 1 - i)) {
return false;
}
}
return true;
}

// 预处理字符串，在两个字符之间加上#
private String preHandleString(String s) {
StringBuffer sb = new StringBuffer();
int len = s.length();
sb.append('#');
for(int i = 0; i < len; i++) {
sb.append(s.charAt(i));
sb.append('#');
}
return sb.toString();
}

// 寻找最长回文字串
public String findLongestPlalindromeString(String s) {
// 先预处理字符串
String str = preHandleString(s);
// 处理后的字串长度
int len = str.length();
// 右边界
int rightSide = 0;
// 右边界对应的回文串中心
int rightSideCenter = 0;
// 保存以每个字符为中心的回文长度一半（向下取整）
int[] halfLenArr = new int[len];
// 记录回文中心
int center = 0;
// 记录最长回文长度
int longestHalf = 0;
for(int i = 0; i < len; i++) {
// 是否需要中心扩展
boolean needCalc = true;
// 如果在右边界的覆盖之内
if(rightSide > i) {
// 计算相对rightSideCenter的对称位置
int leftCenter = 2 * rightSideCenter - i;
// 根据回文性质得到的结论
halfLenArr[i] = halfLenArr[leftCenter];
// 如果超过了右边界，进行调整
if(i + halfLenArr[i] > rightSide) {
halfLenArr[i] = rightSide - i;
}
// 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
if(i + halfLenArr[leftCenter] < rightSide) {
// 直接推出结论
needCalc = false;
}
}
// 中心扩展
if(needCalc) {
while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
halfLenArr[i]++;
} else {
break;
}
}
// 更新右边界及中心
rightSide = i + halfLenArr[i];
rightSideCenter = i;
// 记录最长回文串
if(halfLenArr[i] > longestHalf) {
center = i;
longestHalf = halfLenArr[i];
}
}
}
// 去掉之前添加的#
StringBuffer sb = new StringBuffer();
for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
sb.append(str.charAt(i));
}
return sb.toString();
}

}```

Main.java

```public class Main {

public static void main(String[] args) {

PlalindromeString ps = new PlalindromeString();

String[] testStrArr = new String[] {
"abcdcef",
"aaaabcdefgfedcbaa",
"aaba",
"aaaaaaaaa"
};

for(String str : testStrArr) {
System.out.println(String.format("原字串 : %s", str));
System.out.println(String.format("最长回文串 : %s", ps.findLongestPlalindromeString(str)));
System.out.println();
}

}

}```

0 条评论

• ### tf22: ocr识别——不定长数字串识别

上一篇： 身份证识别——生成身份证号和汉字 代码如下： #!/usr/bin/env python2 # -*- coding: utf-8 -*- """ t...

• ### 基于SIFT特征的图像检索 vs CNN

下面简单的对比一下sift和cnn的检索结果：（基于此改进的版本好多：各种sift；cnn（vgg-fc3；vgg（resnet、inception等）-con...

• ### tf45：tensorflow计算图是如何做的？

MachineLP的Github（欢迎follow）：https://github.com/MachineLP

• ### 1074 宇宙无敌加法器 (20 分)

地球人习惯使用十进制数，并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里，每个数字的每一位都是不同进制的，这种神奇的数字称为“PAT数”。每...

• ### [编程] C语言结构体指针作为函数参数

结构体指针作为函数参数： 结构体变量名代表的是整个集合本身，作为函数参数时传递的整个集合，也就是所有成员，而不是像数组一样被编译器转换成一个指针。如果结构体成员...

• ### C#版[击败98.85%的提交] - Leetcode717. 1比特与2比特字符 - 题解

在线提交: https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/

• ### grafana 介绍与安装、配置

grafana 是一款采用 go 语言编写的开源应用，主要用于大规模指标数据的可视化展现，基于商业友好的 Apache License 2.0 开源协议。是网络...

• ### 洛谷P3346 [ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)

因为所有合法的答案一定是某个叶子节点为根的树上的一条链，因此这样可以统计出所有合法的答案