Является ли этот метод самой длинной общей подстроки правильным?
Я нашел алгоритм для 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
Теперь я ищу максимальную непрерывную последовательность 1
s в каждой диагонали, которая находится в верхнем левом нижнем правом направлении.
Максимальное значение среди них будет ответом.
Я могу выполнить вышеуказанную операцию без использования массива явно. Время сложность все еще O(M*N)
, Таким образом, нет необходимости в памяти.
Кто-нибудь может указать мне, где я иду не так?
2 ответа
Ваш метод правильный. Для доказательства предположим, что самая длинная общая подстрока для 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). Ваше решение может сэкономить некоторую память, если вы используете представление битовой матрицы, в то время как другое решение, вероятно, немного быстрее.