Нахождение наибольшей общей подпоследовательности (Longest Common Subsequence)

# -*- coding: utf-8 -*-
"""
    Нахождение наибольшей общей подпоследовательности (Longest Common Subsequence)
    Реализации алгоритма LCS
    https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
"""
s = []
a = 'nematode knowledge'
b = 'empty bottle'
m = len(a)
n = len(b)
l = [[0 for j in xrange(n+1)]for i in xrange(m+1)]
"""
[[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
for i in reversed(xrange(m)):
    for j in reversed(xrange(n)):
        if a[i] == b[j]:
            l[i][j] = 1 + l[i+1][j+1]
        else:
            l[i][j] = max(l[i+1][j], l[i][j+1])
"""
[[7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [6, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 5, 5, 5, 4, 4, 3, 3, 3, 3, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [4, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 0],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 0],
 [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0],
 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]
"""
i = 0
j = 0
while i < m and j < n:
    if a[i] == b[j]:
        s.append(a[i])
        i += 1
        j += 1
    elif l[i+1][j] >= l[i][j+1]:
        i += 1
    else:
        j += 1
 
"""
    Наибольшая общая подпоследовательность
    l[0][0] = 7
 
    Последовательность
    s = ['e', 'm', 't', ' ', 'o', 'l', 'e']
"""