1 问题，给定一个字符串，求字符串中包含的最大回文子串，要求O复杂度小于n的平方。
首先需要解决奇数偶数的问题，办法是：插入’#‘，aba变成#a#b#a#,变成奇数个，aa变成#a#a#,变成奇数个。
其次要解决指导思想问题，这个方法的切入点是奇数的回文字符串具有对称性，就像圆形一样，所以我们就可以迭代圆心，把具有对称性的点到圆心的距离想象成半径。所以需要两个迭代，一个迭代字符串中的点，另一个从半径为1开始，到超出字符串范围为止迭代字符串的半径。
#!/usr/binp/python
#!coding=utf-8- def max_substr(string):
alist=list(string)
astr='#'+'#'.join(alist)+'#'
br=1
result=''
point = 0
for index in range(len(astr)):
r = longest_r(astr,index)
if r >= br:
br=r
point = index
for i in astr[point-br:point+br+1]:
if i != '#':
result = result + i
return result def longest_r(astr,index):
k=0
for i in range(1,index+1): #此处用1不用0的原因是：astr是加过井号的,所以最小的半径是1
if index+i<len(astr) and index-i>=0 and astr[index-i]==astr[index+i]:
k+=1
else:
break
return k if __name__ == "__main__":
result1=max_substr('a')
print result1
2 优化
上面程序的思想是，在for index in range（len（string））的index中迭代i（也就是半径）每个index都从半径为1开始迭代，直到求出最大的半径，然后返回最大半径对应的点，切片求出回文子串。
如果想优化的话，可以尝试标记目前已知的最大半径，然后index迭代的时候判断如果按照目前的最大半径切片，其是否是回文字符串，如果是，半径加1继续迭代，并且更新目前已知的最大半径，如果不是，那就迭代下一个index，直到最后。