Как ускорить расчет длины длиной общей подстроки?

Question

у меня есть два Очень большие струны и я пытаюсь выяснить их Самая длинная общая подстрока.

Один из способов использования суффикс деревьев (должен иметь очень хорошую сложность, хотя сложную реализацию), а другой Метод динамического программирования (Оба упоминаются на странице Wikipedia, связанной выше).

Используя динамическое программирование

Проблема в том, что метод динамического программирования имеет огромное время работы (сложность O(n*m), куда n а также m длина двух струн).

Что я хочу знать (прежде чем прыгать, чтобы реализовать суффиксные деревья): Можно ли ускорить алгоритм, если я только хочу знать длину общей подстроки (а не общую саму подстроку)?

Answer 1

Это будет быстрее на практике? да. Будет ли это быстрее относительно большого-о? Нет. Динамическое программирование решение всегда o (n * m).

Проблема, в которой вы можете столкнуться с суффиксными деревьями, состоит в том, что вы торгуете линейное сканирование дерева суффикса для огромного наказания в пространстве. Деревья суффикса, как правило, намного больше, чем таблица, которую вам нужно для реализации динамической программирования версии алгоритма. В зависимости от длины ваших струн, все возможное, что динамическое программирование будет быстрее.

Удачи :)

Answer 2

Это заставит его работать быстрее, хотя он все еще будет O(nm).

Одна оптимизация находится в пространстве (которая может сэкономить вам небольшое время распределения), замечал, что LCSuff Только зависит только от предыдущей строки - поэтому, если вы заботитесь о длине, вы можете оптимизировать O(nm) пространство до O(min(n,m)).

Идея состоит в том, чтобы сохранить только два ряда - текущая строка, которую вы обрабатываете, и предыдущая строка, которую вы только что обработали, и выбросите остальные.

Answer 3

Вот простой алгоритм, который может заканчивать в O ((M + N) * log (m + n)), и намного проще реализовать по сравнению с алгоритмом дерева суффикса, который представляет собой o (m + n).

Пусть начнет с минимальной общей длины (MINL) = 0, а максимальная общая длина (MAXL) = min (m + n) +1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

Остальная проблема заключается в том, как удерживать все подстроки длиной l во времени O (n). Вы можете использовать полиномиальную формулу, как следует следующие:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

Майерский битовый вектор алгоритм могу помочь тебе. Работает с использованием манипуляций битов и является гораздо более быстрым подходом.