-
-
-
-
-
1. 最长回文子串
class Solution(object):
def longestPalindrome(self, s):
"""
:type s: str
:rtype: str
"""
longest = 0
max_len=0
for i in xrange(len(s)):
if self.isP(s[i - max_len:i+1]):
longest = i - max_len
# print 'longest 1:',longest
max_len = max_len + 1
# print 'max_len 1 :',max_len
elif i - max_len - 1 >= 0 and self.isP(s[i-max_len-1:i+1]):
longest = i - max_len - 1
max_len = max_len + 2
return s[longest:longest+max_len]
def isP(self,s):
# print s
return s == s[::-1]
solu = Solution()
print solu.longestPalindrome("xxABCDCBAio")
2. KMP
def mykmp(s,p):
i,j,m,n,nextarr = -1,0,len(s),len(p),[-1]*len(p)
while j<n-1:
if i==-1 or p[i]==p[j]:
i,j = i+1,j+1
nextarr[j]=i
else:
i = nextarr[i]
i,j=0,0
while i<m and j<n:
if j==-1 or s[i]==p[j]:
i,j = i+1,j+1
else:j = nextarr[j]
if j==n:
return i-j
return -1
# print mykmp('abaabcaba','abc')
3. 最长递增子序列
def lcs_result(c,X,i,j):
if i==0 or j==0:return
if c[i][j] == c[i-1][j-1]+1:
lcs_result(c,X,i-1,j-1)
print X[i-1]
elif c[i][j] == c[i-1][j]:
lcs_result(c,X,i-1,j)
else:
lcs_result(c,X,i,j-1)
def lcs_length(s1,s2):
m,n = len(s1),len(s2)
c=[[0 for i in range(n+1)] for i in range(m+1)]
# c = [[0]*(n+1)]*(m+1)
# print c==c1
for i in range(m):
for j in range(n):
if s1[i]==s2[j]:
c[i+1][j+1] = c[i][j]+1
else:
c[i+1][j+1] = max(c[i+1][j],c[i][j+1])
return c
x = 'ABCBDAB'
y = 'BDCABA'
c = lcs_length(x,y)
lcs_result(c,'ABCBDAB',len(x),len(y))
