Как ускорить расчет длины самой длинной общей подстроки?
У меня есть две очень больших строки, и я пытаюсь узнать их Самую Длинную Общую Подстроку.
Один путь использует суффиксные деревья (предполагаемый иметь очень хорошую сложность, хотя сложная реализация), и другой является методом динамического программирования (оба упоминаются на странице Wikipedia, связанной выше).
Используя динамическое программирование
Проблема состоит в том, что метод динамического программирования имеет огромное время выполнения (сложность O(n*m), где n и m длины двух строк).
Что я хочу знать (прежде чем, переходя для реализации суффиксных деревьев): действительно ли возможно ускорить алгоритм, если я только хочу знать длину общей подстроки (а не самой общей подстроки)?
2 ответа
Будет ли это быстрее на практике? да. Будет ли быстрее в отношении Big-Oh? Нет. Решение динамического программирования всегда O (n * m).
Проблема, с которой вы можете столкнуться с суффиксными деревьями, заключается в том, что вы обмениваете линейное временное сканирование суффиксного дерева на огромный штраф в пространстве. Деревья суффиксов обычно намного больше, чем таблица, которую вам нужно реализовать для версии алгоритма динамического программирования. В зависимости от длины ваших строк вполне возможно, что динамическое программирование будет быстрее.
Удачи :)
Это заставит его работать быстрее, хотя он все равно будет O (нм) .
Одна оптимизация выполняется в пространстве (что может сэкономить вам немного времени на выделение памяти). Замечено, что LCSuff зависит только от предыдущей строки - поэтому, если вас интересует только длина, вы можете оптимизировать O (нм) до O (min (n, m)) .
Идея состоит в том, чтобы оставить только две строки - текущую строку, которую вы обрабатываете, и предыдущую строку, которую вы только что обработали, а остальные выбросить.