最长公共子串和子序列的Python实现，带图示。

使用矩阵来记录两个子串之间各个字符之间的对应关系。

最长子串：矩阵中数字最大的就是最长子串的长度。若对应位置字符相同，则c[i][j] = c[i-1][j-1] + 1

 def longSubStr(str1,str2):

     len1 = len(str1)

     len2 = len(str2)

     longest,start1,start2 = 0,0,0

     c = [[0 for i in range(len2+1)]for i in range(len1+1)]

     for i in range(len1+1):

         for j in range(len2+1):

             if i == 0 or j == 0:

                 c[i][j] = 0

             elif str1[i-1] == str2[j-1]:

                 c[i][j] = c[i-1][j-1]+1

             else:

                 c[i][j] = 0

             if (longest < c[i][j]):

                 longest = c[i][j]

                 start1 = i-longest

                 start2 = j-longest

     return str1[start1:start1+longest],start1,start2

最长子序列：若对应位置字符相同，则c[i][j] = c[i-1][j-1] + 1，若不同，则max(c[i][j-1],c[i-1][j]).

 def printLcs(flag,a,i,j):

     if i==0 or j==0:

         return

     if flag[i][j]=='OK':

         printLcs(flag,a,i-1,j-1)

         print a[i-1],

     elif flag[i][j]=='Left':

         printLcs(flag,a,i,j-1)

     else:

         printLcs(flag,a,i-1,j)

 def longSubSeq(str1,str2):

     len1 = len(str1)

     len2 = len(str2)

     longest = 0

     c = [[0 for i in range(len2+1)]for i in range(len1+1)]

     flag = [[0 for i in range(len2+1)]for i in range(len1+1)]

     for i in range(len1+1):

         for j in range(len2+1):

             if i == 0 or j == 0:

                 c[i][j] = 0

             elif str1[i-1] == str2[j-1]:

                 c[i][j] = c[i-1][j-1]+1

                 flag[i][j] = 'OK'

                 longest = max(longest,c[i][j])

             elif c[i][j-1] > c[i-1][j]:

                 c[i][j] =c[i][j-1]

                 flag[i][j] = 'Left'

             else:

                 c[i][j] =c[i-1][j]

                 flag[i][j] = 'UP'

     printLcs(flag,str1,len1,len2)

     return longest

 a='ABCBDAB'

 b='BDCABA'

 print longSubSeq(a,b)