Как найти самую большую подстроку среди двух строк?

Question

Как найти наибольшую ОБЩУЮ подстроку среди двух строк?

Answer 1

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

Answer 2

Я думаю, что вы можете решить эту проблему, используя довольно элегантный алгоритм динамического программирования, который выполняется за время O (mn) и пространство O (mn), где m и n - количество символов в каждой строке.Идея основана на следующем повторении.Пусть две строки: A = a ₀ a ₁ a ₂ ... a _n-1 и B = b ₀ b ₁ b ₂ ... b _m-1 и посмотрите на их первые символы a ₀ и b ₀ .Тогда есть три способа найти самую длинную общую подпоследовательность:

1. Если первые символы равны, одним из вариантов будет найти самые длинные общие подпоследовательности остальных двух строк, тогдачтобы добавить первый символ к совпадению.
2. В качестве альтернативы, вы можете решить не совпадать с первыми двумя символами.В этом случае одним из вариантов будет посмотреть, какую самую длинную общую подпоследовательность вы можете создать, игнорируя первый символ первой строки.3 Наконец, вы также можете игнорировать первый символ второй строки.

Это дает нам очень хорошее повторение:

LCS(A[0 .. n], B[0 .. m]) = longest of {
  A[0] + LCS(A[1 .. n], B[1 .. m])   (if A[0] == B[0]),
         LCS(A[1 .. n], B[0 .. m]),
         LCS(A[0 .. n], B[1 .. m])
    }

В качестве наших базовых случаев самая длинная общая подстрокалюбой строки, а пустая строка - пустая строка:

LCS (A[n .. n], B[i, m]) = ""
LCS (A[i .. n], B[m, m]) = ""

Это определение самой длинной общей подстроки позволяет вычислить значение LCS (A [i .. n], B [j ..m]) с учетом трех значений LCS (A [i + 1 .. n], B [j + 1 ... m]), LCS (A [i .. n], B [j + 1 ... m])и LCS (A [i + 1 .. n], B [j ... m]).Следовательно, если вы вычисляете эти значения в правильном порядке, вы можете просто заполнить таблицу результатами за один проход и построить результат оттуда.Используя некоторые стандартные трюки DP, это можно сделать для запуска в O (mn).

Answer 3

В основном два способа: 1. динамическое программирование, которое стоит O (mn) времени и O (mn) пространства. "templatetypedef" ответил на это. 2. дерево суффиксов, по этому вам нужно сначала его построить, процесс сборки с суффиксной ссылкой будет O (m + n) (время и пространство), если без суффиксной ссылки O ((m + n) ^ 2) (время ). Хотя процесс построения дерева суффиксов в лучшем случае эффективен при динамическом программировании, однако после его построения можно получить самую длинную общую подстроку за время O (k) (k - длина LCS).