# -*- 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'] """
четверг, 18 сентября 2014 г.
Нахождение наибольшей общей подпоследовательности (Longest Common Subsequence)
Подписаться на:
Сообщения
(
Atom
)