Правилен ли этот метод самой длинной общей подстроки?

Question

Я нашел алгоритм Самая длинная общая подстрока.Обычно это делается с помощью 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

Теперь я ищу максимальную непрерывную последовательность 1s на каждой диагонали, которая находится в направлении от верхнего левого угла к нижнему правому.

Максимальное значение среди них и будет ответом.

Я могу выполнить описанную выше операцию без явного использования массива.Временная сложность все еще O(M*N).Так что память не нужна.

Может ли кто-нибудь указать мне, где я ошибаюсь?

Answer 1

Ваш метод правильный.Для доказательства предположим, что самая длинная общая подстрока для 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])

как вы можете видеть, элементы текущей строки зависят только от элементов непосредственно верхней строки.

Answer 2

Ваш алгоритм верен, но стандартный подход DP исключает второй этап и упрощает решение.

Вместо того, чтобы отмечать логические значения и затем сканировать диагонали в поисках самых длинных последовательностей, вы можете вычислять длины диагоналей при построении матрицы — требуется только один проход.

С точки зрения временной и пространственной сложности оба решения имеют размер O(NxM).Ваше решение может сэкономить немного памяти, если вы используете бит-матричное представление, в то время как другое решение, вероятно, будет немного быстрее.