Наибольшая общая подстрока: различия между версиями

[отпатрулированная версия]

Содержимое удалено Содержимое добавлено

Линейный

Текущая версия от 07:23, 11 марта 2020

Наибольшая общая подстрока (англ. longest common substring) — подстрока двух или более строк, имеющая максимальную длину.

Формально, наибольшей общей подстрокой строк $s_{1},s_{2},\ldots s_{n}$ называется строка $\left.w^{*}\right.$ , которая удовлетворяет условию $\|w^{*}\|=\max(\{\|w\||w\sqsubseteq s_{i},i=1,\ldots n\})$ , операция $w\sqsubseteq s_{i}$ обозначает что строка $\left.w\right.$ является (возможно несобственной) подстрокой строки $\left.s_{i}\right.$ .

Решение задачи поиска наибольшей общей подстроки для двух строк $\left.s_{1}\right.$ и $\left.s_{2}\right.$ , длины которых $\left.m\right.$ и $\left.n\right.$ соответственно, заключается в заполнении таблицы $\left.A_{ij}\right.$ размером $(m+1)\times (n+1)$ по следующему правилу, принимая, что символы в строке нумеруются от единицы.

$\left\{{\begin{array}{rclr}A_{0j}&=&0,&j=0\ldots n,\\A_{i0}&=&0,&i=0\ldots m,\\A_{ij}&=&0,&s_{1}[i]\neq s_{2}[j],i\neq 0,j\neq 0,\\A_{ij}&=&A_{i-1j-1}+1,&s_{1}[i]=s_{2}[j],i\neq 0,j\neq 0.\end{array}}\right.$

Максимальное число $\left.A_{uv}\right.$ в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

$s_{1}[u-A_{uv}+1]\ldots s_{1}[u]$ и $s_{2}[v-A_{uv}+1]\ldots s_{2}[v]$ .

В таблице заполнены значения для строк SUBSEQUENCE и SUBEUENCS:

   SUBSEQUENCE
  000000000000
S 010010000000
U 002000010000
B 000300000000
E 000001001001
U 001000010000
E 000001002001
N 000000000300
C 000000000040
S 010010000000

Получаем наибольшую общую подстроку UENC.

Сложность такого алгоритма составляет O(mn).

См. также

Примечания

@@ Строка 1: / Строка 1: @@
-[[Наибольшая общая подстрока|Наибольшая общая подстрока (longest common substring)]] — подстрока двух или более строк, имеющая максимальную длину.
+'''Наибольшая общая подстрока''' ({{lang-en|longest common substring}}) — подстрока двух или более строк, имеющая максимальную длину.
 Формально, наибольшей общей [[Подстрока|подстрокой]] строк <math>s_1,s_2,\ldots s_n</math> называется строка <math>\left.w^*\right.</math>, которая удовлетворяет условию <math>\|w^*\| = \max(\{\|w\||w\sqsubseteq s_i, i=1,\ldots n\})</math>, операция <math>w\sqsubseteq s_i</math> обозначает что строка <math>\left.w\right.</math> является (возможно несобственной) подстрокой строки <math>\left.s_i\right.</math>.
+Решение задачи поиска наибольшей общей подстроки для двух строк <math>\left.s_1\right.</math> и <math>\left.s_2\right.</math>, длины которых <math>\left.m\right.</math> и <math>\left.n\right.</math> соответственно, заключается в заполнении таблицы <math>\left.A_{ij}\right.</math> размером <math>(m+1)\times (n+1)</math> по следующему правилу, принимая, что символы в строке нумеруются от единицы.
-==Алгоритмы поиска наибольшей общей подстроки==
-===Наивный алгоритм===
-Решение задачи поиска наибольшей общей подстроки для двух строк <math>\left.s_1\right.</math> и <math>\left.s_2\right.</math>, длины которых <math>\left.m\right.</math> и <math>\left.n\right.</math> соответственно, заключается в заполнении таблицы <math>\left.A_{ij}\right.</math> размером <math>(m+1)\times (n+1)</math> по следующему правилу, принимая, что символы в строке нумеруются от единицы.
 <math>\left\{
@@ Строка 19: / Строка 17: @@
 Максимальное число <math>\left. A_{uv} \right. </math> в таблице это и есть длина наибольшей общей подстроки, сама подстрока:
-<math>s_1[u-A_{uv}+1]\ldots s_1[u]</math> и <math>s_2[v-A_{uv}+1]\ldots s_2[vu]</math>.
+<math>s_1[u-A_{uv}+1]\ldots s_1[u]</math> и <math>s_2[v-A_{uv}+1]\ldots s_2[v]</math>.
 В таблице заполнены значения для строк '''SUBSEQUENCE''' и '''SUBEUENCS''':
     '''SUBSEQUENCE'''
@@ Строка 32: / Строка 30: @@
  '''E''' 00000'''1'''00'''2'''00'''1'''
  '''N''' 000000000'''3'''00
- '''C''' 0000000000'''4'''0
+ '''C''' 0000000000<font color="red">'''4'''</font>0
  '''S''' 0'''1'''00'''1'''0000000
- Получаем наибольшую общую подстроку '''UENC'''
+Получаем наибольшую общую подстроку '''UENC.'''
-Очевидно, трудоемкость такого алгоритма составляет ''[[«O» большое и «o» малое|O]](mn)''.
+Сложность такого алгоритма составляет ''[[«O» большое и «o» малое|O]](mn)''.
-=== Реализация на Haskell ===
-<source lang="Haskell">
-import Data.List
-import Data.Function
-lcstr xs ys = maximumBy (compare `on` length) . concat $ [find xs' ys | xs' <- tails xs] ++ [find xs ys' | ys' <- drop 1 $ tails ys]
-  where find xs ys = scanl grow [] $ zip xs ys
-        grow z (x, y) = if x == y then z ++ [x] else []
-</source>
-===Алгоритм, использующий [[суффиксное дерево]]===
 == См. также ==
 * [[Суффиксное дерево]]
@@ Строка 55: / Строка 42: @@
 * [[Наибольшая общая подпоследовательность]]
+== Примечания ==
-{{math-stub}}
+{{примечания}}{{Строки}}{{нет ссылок|дата=7 июня 2019}}
 [[Категория:Строковые алгоритмы]]
-[[en:Longest common substring problem]]

Строки
Меры схожести строк	Расстояние Дамерау — Левенштейна Расстояние Левенштейна Расстояние Хэмминга Сходство Джаро — Винклера
Поиск подстроки	Алгоритм Бойера — Мура Алгоритм Бойера — Мура — Хорспула Алгоритм Кнута — Морриса — Пратта Алгоритм Рабина — Карпа Префикс-функция Z-функция Алгоритм Ахо — Корасик
Палиндромы	Дерево палиндромов Алгоритм Манакера
Выравнивание последовательностей	Алгоритм Нидлмана — Вунша Алгоритм Смита — Ватермана
Суффиксные структуры	Суффиксный массив Суффиксный автомат Суффиксное дерево Префиксное дерево
Другое	Синтаксический анализ Сопоставление с образцом Наибольшая общая подпоследовательность Наибольшая общая подстрока

Наибольшая общая подстрока: различия между версиями

Текущая версия от 07:23, 11 марта 2020

См. также

Примечания

Навигация

Поиск