Самая длинная общая проблема с подстрокой

В Викиучебнике есть книга по темам: Реализация алгоритма / Строки / Самая длинная общая подстрока

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

Пример [ править ]

Самая длинная общая подстрока строк «ABABC», «BABCA» и «ABCBA» - это строка «ABC» длины 3. Другие общие подстроки: «A», «AB», «B», «BA», «BC». и «С».

 ABABC ||| BABCA ||| ABCBA

Определение проблемы [ править ]

Для двух строк, длины и длины , найдите самую длинную строку, которая является подстрокой обоих и .${\ displaystyle S}$${\ displaystyle m}$${\ displaystyle T}$${\ displaystyle n}$${\ displaystyle S}$${\ displaystyle T}$

Обобщением является проблема k-общих подстрок . Учитывая набор строк , где и . Найдите для каждой самые длинные строки, которые встречаются как подстроки как минимум строк.${\ Displaystyle S = \ {S_ {1}, ..., S_ {K} \}}$${\ displaystyle | S_ {i} | = n_ {i}}$${\ displaystyle \ Sigma n_ {i} = N}$${\ Displaystyle 2 \ Leq K \ Leq K}$${\ displaystyle k}$

Алгоритмы [ править ]

Длины и начальные позиции наиболее длинных общих подстрок и по времени можно найти с помощью обобщенного суффиксного дерева . Их поиск по затратам на динамическое программирование . Решения обобщенной проблемы занимают пространство и · ... · время при динамическом программировании и требуют времени при использовании обобщенного суффиксного дерева .${\ displaystyle S}$${\ displaystyle T}$${\ displaystyle \ Theta}$${\ Displaystyle (п + т)}$${\ Displaystyle \ Theta (нм)}$${\ displaystyle \ Theta (n_ {1} + ... + n_ {K})}$${\ Displaystyle \ Theta (п_ {1}}$${\ displaystyle n_ {K})}$${\ Displaystyle \ Theta (Н * К)}$

Суффиксное дерево [ править ]

Обобщенное суффиксное дерево для строк «ABAB», «BABA» и «ABBA», пронумерованных 0, 1 и 2.

Самые длинные общие подстроки набора строк можно найти, построив обобщенное суффиксное дерево для строк, а затем найдя самые глубокие внутренние узлы, которые имеют листовые узлы из всех строк в поддереве под ним. На рисунке справа показано дерево суффиксов для строк «ABAB», «BABA» и «ABBA», дополненное уникальными ограничителями строки, которые превращаются в «ABAB $ 0», «BABA $ 1» и «ABBA $ 2». Узлы, представляющие «A», «B», «AB» и «BA», имеют дочерние листья из всех строк, пронумерованные 0, 1 и 2.

Построение дерева суффиксов требует времени (если размер алфавита постоянный). Если пройти по дереву снизу вверх с помощью битового вектора, указывающего, какие строки видны под каждым узлом, проблема k-общих подстрок может быть решена вовремя. Если суффиксное дерево подготовлено для поиска наименьшего общего предка с постоянным временем , оно может быть решено вовремя. ^[1]${\ Displaystyle \ Theta (N)}$${\ Displaystyle \ Theta (NK)}$${\ Displaystyle \ Theta (N)}$

Динамическое программирование [ править ]

Следующий псевдокод находит набор самых длинных общих подстрок между двумя строками с помощью динамического программирования:

функция LCSubstr (S [1..r], T [1..n]) L: = массив (1..r, 1..n) z: = 0 ret: = {} для i: = 1..r для j: = 1..n, если S [i] = T [j], если i = 1 или j = 1 L [i, j]: = 1 еще L [i, j]: = L [i - 1, j - 1] + 1 если L [i, j]> z z: = L [i, j] ret: = {S [i - z + 1..i]} иначе,  если L [i, j] = z ret: = ret ∪ {S [i - z + 1..i]} еще L [i, j]: = 0 возвращение в отставке

Этот алгоритм работает во времени. Массив хранит длинную общая подпоследовательность префиксов и которые заканчиваются в положении , , соответственно. Переменная используется для хранения длины самой длинной найденной общей подстроки. Набор используется для удержания набора длинных струн . Набор можно эффективно сохранить, просто сохранив индекс , который является последним символом самой длинной общей подстроки (размера z) вместо . Таким образом , все длинные общие подстроки бы, для каждого I в , .${\ displaystyle O (nr)}$LS[1..i]T[1..j] S[i]T[j]zretzretiS[i-z+1..i]retS[(ret[i]-z)..(ret[i])]

Следующие приемы можно использовать для уменьшения использования памяти реализацией:

• Сохраняйте только последнюю и текущую строку таблицы DP для экономии памяти ( вместо )${\ Displaystyle О (\ мин (г, п))}$${\ displaystyle O (nr)}$
• Храните в строках только ненулевые значения. Это можно сделать с помощью хеш-таблиц вместо массивов. Это полезно для больших алфавитов.

См. Также [ править ]

• Самая длинная палиндромная подстрока
• n -грамма , все возможные подстроки длины n , содержащиеся в строке

Ссылки [ править ]

Внешние ссылки [ править ]

В реализации алгоритма Викибука есть страница на тему: Самая длинная общая подстрока

• Словарь алгоритмов и структур данных: самая длинная общая подстрока
• Perl / XS реализация алгоритма динамического программирования
• Perl / XS реализация алгоритма суффиксного дерева
• Реализации динамического программирования на разных языках в викиучебниках
• рабочая AS3 реализация алгоритма динамического программирования
• Реализация C на основе суффиксного дерева самой длинной общей подстроки для двух строк