Наибольшая общая подстрока

1-01-2022, 11:00

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

Формально, наибольшей общей подстрокой строк s 1 , s 2 , … s n {displaystyle s_{1},s_{2},ldots s_{n}} называется строка w ∗ {displaystyle left.w^{*} ight.} , которая удовлетворяет условию ‖ w ∗ ‖ = max ( { ‖ w ‖ | w ⊑ s i , i = 1 , … n } ) {displaystyle |w^{*}|=max({|w||wsqsubseteq s_{i},i=1,ldots n})} , операция w ⊑ s i {displaystyle wsqsubseteq s_{i}} обозначает что строка w {displaystyle left.w ight.} является (возможно несобственной) подстрокой строки s i {displaystyle left.s_{i} ight.} .

Решение задачи поиска наибольшей общей подстроки для двух строк s 1 {displaystyle left.s_{1} ight.} и s 2 {displaystyle left.s_{2} ight.} , длины которых m {displaystyle left.m ight.} и n {displaystyle left.n ight.} соответственно, заключается в заполнении таблицы A i j {displaystyle left.A_{ij} ight.} размером ( m + 1 ) × ( n + 1 ) {displaystyle (m+1) imes (n+1)} по следующему правилу, принимая, что символы в строке нумеруются от единицы.

{ A 0 j = 0 , j = 0 … n , A i 0 = 0 , i = 0 … m , A i j = 0 , s 1 [ i ] ≠ s 2 [ j ] , i ≠ 0 , j ≠ 0 , A i j = A i − 1 j − 1 + 1 , s 1 [ i ] = s 2 [ j ] , i ≠ 0 , j ≠ 0. {displaystyle left{{egin{array}{rclr}A_{0j}&=&0,&j=0ldots n,A_{i0}&=&0,&i=0ldots m,A_{ij}&=&0,&s_{1}[i] eq s_{2}[j],i eq 0,j eq 0,A_{ij}&=&A_{i-1j-1}+1,&s_{1}[i]=s_{2}[j],i eq 0,j eq 0.end{array}} ight.}

Максимальное число A u v {displaystyle left.A_{uv} ight.} в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

s 1 [ u − A u v + 1 ] … s 1 [ u ] {displaystyle s_{1}[u-A_{uv}+1]ldots s_{1}[u]} и s 2 [ v − A u v + 1 ] … s 2 [ v ] {displaystyle 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).


  • Числа Пизо
  • Континуанта
  • Континуанта
  • Хеммингова сфера
  • Артинов модуль

  •  

    • Яндекс.Метрика
    • Индекс цитирования