Является ли этот метод самой длинной общей подстроки правильным?

Question

Я нашел алгоритм для Longest Common Substring. Обычно это делается с помощью 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). Ваше решение может сэкономить некоторую память, если вы используете представление битовой матрицы, в то время как другое решение, вероятно, немного быстрее.