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

Question

У меня есть две очень большие строки , и я пытаюсь выяснить их Longest Common Substring .

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

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

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

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

Answer 1

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

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

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

Answer 2

Будет ли это быстрее на практике? Да. Будет ли это быстрее в отношении Big-Oh? Нет. Решением динамического программирования всегда является O (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

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