Правилен ли этот метод самой длинной общей подстроки?
-
23-12-2019 - |
Вопрос
Я нашел алгоритм Самая длинная общая подстрока.Обычно это делается с помощью dynamic programming
, используя двумерный массив размером mxn
где m
и n
— длины двух рассматриваемых строк.
Я построю следующую матрицу для двух строк.
M[i][j] = 1 if s1[i]==s2[j] else 0.
Например, если строки: abcxy
и pqaabx
Матрица выглядит следующим образом:
a b c x y
p 0 0 0 0 0
q 0 0 0 0 0
a 1 0 0 0 0
a 1 0 0 0 0
b 0 1 0 0 0
x 0 0 0 1 0
Теперь я ищу максимальную непрерывную последовательность 1
s на каждой диагонали, которая находится в направлении от верхнего левого угла к нижнему правому.
Максимальное значение среди них и будет ответом.
Я могу выполнить описанную выше операцию без явного использования массива.Временная сложность все еще O(M*N)
.Так что память не нужна.
Может ли кто-нибудь указать мне, где я ошибаюсь?
Решение
Ваш метод правильный.Для доказательства предположим, что самая длинная общая подстрока для S1 и S2 взята из S1[i..j] и S2[p..q].Это подразумевает s1 [i+k] = s2 [p+k
Все они лежат на диагонали, начиная с (i,p).
Решение динамического программирования делает то же самое, но вместо того, чтобы сначала вычислять таблицу и проходить по диагональным путям, оно вычисляет таблицу в зависимости от ее диагонального родителя, а также от того, совпадают ли они или нет.
ОТРЕДАКТИРОВАНО
По вашему комментарию в Википедии решение с использованием дополнительной памяти.Это здесь только для ясности.В принципе вам нужно только две строки матрицы в решении Википедии и сохранить текущий максимальный счетчик в одной переменной.Это верно, поскольку для любого (i,j)-го элемента матрицы
M(i,j) = 1 + M(i-1, j-1) (если s1[i] == s2[j])
как вы можете видеть, элементы текущей строки зависят только от элементов непосредственно верхней строки.
Другие советы
Ваш алгоритм верен, но стандартный подход DP исключает второй этап и упрощает решение.
Вместо того, чтобы отмечать логические значения и затем сканировать диагонали в поисках самых длинных последовательностей, вы можете вычислять длины диагоналей при построении матрицы — требуется только один проход.
С точки зрения временной и пространственной сложности оба решения имеют размер O(NxM).Ваше решение может сэкономить немного памяти, если вы используете бит-матричное представление, в то время как другое решение, вероятно, будет немного быстрее.