题目
最近在微信公众号里看看到了一个PPTV的面试算法题，感觉难度适中，想试下。题目的内容为求一个字符串的最长对称子字符串。如：
输入 输出
abba 4
abad 3
acccbaa 3
我的算法1
自己反复思索了许多时间。一开始是觉得可以利用对称字符串的一个特点，就是反转前后两者是一样的。所以有如下的算法：
最长子串长度为max_sub_len
- 1 把输入的字符串a,进行反转得到b
- 2 把b与a首尾对齐
- 3 找当前相同位置上a与b相同的元素，比如a[0]与b[0], a[1]与b[1],….,a[n]与b[n]，找到最长连续相等的长度，记录此时最长的子串长度长度tmp_max_sub_len。取max_sub_len与tmp_max_sub_len中大者赋给max_sub_len。
- 4 把a左移动一位，如果已经到达a[n]与b[0]对齐时，退出.a[1]与b[0]对齐。重复第3步。
等到算法完成时，max_sub_len就是最长的子对称子串长度。
拿hello为例试下：
1，2
a = hello
b = olleh
3 找到a[2]=b[2]=l 最长连续相等为1
4
a = ello
b = olleh
3 找到a[1]=b[0] a[2]=b[1] 最长连接相等为2
4
a = llo
b = elleh
3 找到最长连续相等为1。
4
a = lo
b = elleh
3 找到最长连续相等数为0。
4
a = o
b = elleh
到达终点算法退出。得到最长对称子串长度为2。
时间复杂度：比较次数为n + (n-1) + (n-2) + … + 1 = n(n-1)/2 = O(n^2)
空间复杂度：可以通过索引的转化，实现只使用原数组。空间复杂度为O(n)
微信评论里的算法
有同学在评论里说，可以把反转后的a和b放在一起，求它们的最长公共子串。求最长公共子串的算法属于动态规划的算法，比较复杂，它的实现中，时间复杂度也是O(n^2)。没有我的算法1来得直接简单。具体实现我就不说了。
我的算法2
第一种算法算得上不错了。却不是最好的。因为它的时间复杂度n^2的系数为0.5,比较大。下面给出一种更好的算法。
对对称的情况进行分类。
奇对称的：aba类型的。
偶对称的：abba类型的。
第二种算法是根据两种类型的不同，以当前字符为中心向两侧辐射，比较对称两个字符。从而得到最长的对称子串。
不再描述其算法，直接上代码（我的github——algorithm_ds）。这种算法在最坏的情况下，是aaaaaaaaaaaa，全是一个字符的字符串。要比较n(n-1)次。正常随机输入的情况下,o(n^2)的系数是很小的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #! /usr/bin/python
# -*- coding: utf-8 -*-
'''
最长对称子字符串有两种形式
奇对称：abcba
偶对称：abccba
算法的时间复杂度为n^2
空间复杂度为n
'''
#写一个循环方便测试
while (True):
max_sym_sub_len = 1
max_single = 1 #奇对称最长子串
max_double = 0 #偶对称最长子串
raw_str = raw_input()
# pdb.set_trace()
if raw_str == 'q': #退出
break;
if (len(raw_str) == 1):
pass
elif (len(raw_str) == 2):
if (raw_str[0] == raw_str[1]): #长度为2,两个字符相等，最长子串为2
max_sym_sub_len = 2
else: #长度>3
start_ind = 1 #从第2个字符开始判断
tmp_ind = 0
#奇对称的情形
for start_ind in range(1, len(raw_str) - 1):
max_single_tmp = 1
# 判断当前的字符距离哪个端点更近
tmp_range = min(start_ind, len(raw_str) - 1 - start_ind)
# print start_ind, tmp_range
for tmp_ind in range(1, tmp_range + 1):
#开始判断,如果两侧的字符相等，临时最长的长度加2
if (raw_str[start_ind - tmp_ind] == raw_str[start_ind + tmp_ind]):
max_single_tmp += 2
else:
break;
max_single = max(max_single, max_single_tmp)
for start_ind in range(1, len(raw_str) - 1):
max_double_tmp = 0
# 判断当前的字符距离第一个字符，和当前字符的下个字符距离
# 最后一个端点的距离中哪个更近
tmp_range = min(start_ind, len(raw_str) - 2 - start_ind)
# print start_ind, tmp_range
# tmp_ind 应该从0开始
for tmp_ind in range(tmp_range + 1):
#开始判断,如果两侧的字符相等，临时最长的长度加2
if (raw_str[start_ind - tmp_ind] ==
raw_str[start_ind + 1 + tmp_ind]):
max_double_tmp += 2
else:
break;
max_double= max(max_double, max_double_tmp)
max_sym_sub_len = max(max_single, max_double)
print max_sym_sub_len
|