Самая длинная общая подстрока без динамического программирования или суффиксного дерева
Руководство по разработке алгоритмов Skiena, вопрос 8-3, часть b, просит дать «более простой» алгоритм BigO (nm) для нахождения самой длинной общей подстроки, которая не зависит от динамического программирования. Очевидный ответ, по-видимому, заключается в использовании дерева суффиксов, однако, Skiena использует слово «проще». Я не уверен, что деревья суффиксов проще, чем DP, возможно, поиск проще, но построение дерева суффиксов с временной сложностью нм совсем не просто. Итак, мне интересно, есть ли другой способ решить эту проблему за O (нм) времени?
Решение
Допустим, мы зафиксировали стартовую позицию i в первой (более короткой) строке s, Теперь давайте найдем его самый длинный префикс в более длинной строке. Это может быть сделано в O(n + m) изучив функция префикса(или же функция z) строки s[i:] + # + t где # — специальный символ, который не существует ни в одном из s а также t,
Общая сложность O(n(n + m)) который O(nm) если н < м
Другие решения
Других решений пока нет …