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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м оформление
м Checkwiki #1. Исправление избыточного префикса "Шаблон:"
 
(не показано 29 промежуточных версий 27 участников)
Строка 1: Строка 1:
[[Наибольшая общая подстрока|Наибольшая общая подстрока ({{lang-en|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>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\{
<math>\left\{
Строка 19: Строка 17:
Максимальное число <math>\left. A_{uv} \right. </math> в таблице это и есть длина наибольшей общей подстроки, сама подстрока:
Максимальное число <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''' и '''SUBEUENCS''':


'''SUBSEQUENCE'''
'''SUBSEQUENCE'''
Строка 35: Строка 33:
'''S''' 0'''1'''00'''1'''0000000
'''S''' 0'''1'''00'''1'''0000000
Получаем наибольшую общую подстроку '''UENC'''
Получаем наибольшую общую подстроку '''UENC.'''


Очевидно, трудоемкость такого алгоритма составляет ''[[«O» большое и «o» малое|O]](mn)''.
Сложность такого алгоритма составляет ''[[«O» большое и «o» малое|O]](mn)''.

==== Реализация на C++ ====
<source lang="cpp">void GetLargestCommonSubstring(string & result, const string & a, const string & b)
{
const int a_length = a.size();
const int b_length = b.size();
int max_length = 0;
int result_index = 0;
vector<int> solution(b_length + 1, 0);
for(int i = a_length - 1; i >= 0; i--)
{
const vector<int> prev_solution = solution;
for(int j = b_length - 1; j >= 0; j--)
{
if(a[i] != b[j])
solution[j] = 0;
else
{
const int length = 1 + prev_solution[j + 1];
if (length > max_length)
{
max_length = length;
result_index = i;
}
solution[j] = length;
}
}
}
result = a.substr(result_index, max_length);
}</source>

==== Реализация на C# ====
<!-- // в английской версии статьи
//http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring
// num имет тип int[,], но этот вариант
//вылетает по памяти при больших размерах, на аллокации памяти
//по этому была сделаны модификация -->
<source lang="csharp">
public static int LongestCommonSubstring( string str1, string str2 )
{
if( String.IsNullOrEmpty( str1 ) || String.IsNullOrEmpty( str2 ) )
return 0;

List<int[]> num = new List<int[]>();
int maxlen = 0;
for( int i = 0; i < str1.Length; i++ )
{
num.Add( new int[ str2.Length ] );
for( int j = 0; j < str2.Length; j++ )
{
if( str1[ i ] != str2[ j ] )
num[ i ][ j ] = 0;
else
{
if( ( i == 0 ) || ( j == 0 ) )
num[ i ][ j ] = 1;
else
num[ i ][ j ] = 1 + num[ i - 1 ][ j - 1 ];
if( num[ i ][ j ] > maxlen )
maxlen = num[ i ][ j ];
}
if( i >= 2 )
num[ i - 2 ] = null;
}
}
return maxlen;
}
</source>

==== Реализация на Haskell ====
<source lang="Haskell">
import Data.List
import Data.Function

lcstr xs ys = maximumBy (compare `on` length) . concat $ [f xs' ys | xs' <- tails xs] ++ [f xs ys' | ys' <- drop 1 $ tails ys]
where f xs ys = scanl g [] $ zip xs ys
g z (x, y) = if x == y then z ++ [x] else []
</source>

===Алгоритм, использующий [[суффиксное дерево]]===


== См. также ==
== См. также ==
Строка 129: Строка 42:
* [[Наибольшая общая подпоследовательность]]
* [[Наибольшая общая подпоследовательность]]


== Примечания ==
{{math-stub}}
{{примечания}}{{Строки}}{{нет ссылок|дата=7 июня 2019}}


[[Категория:Строковые алгоритмы]]
[[Категория:Строковые алгоритмы]]

[[en:Longest common substring problem]]
[[pl:Najdłuższy wspólny podłańcuch]]
[[vi:Bài toán xâu con chung dài nhất]]

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

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

Формально, наибольшей общей подстрокой строк называется строка , которая удовлетворяет условию , операция обозначает что строка является (возможно несобственной) подстрокой строки .

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

Максимальное число в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

и .

В таблице заполнены значения для строк 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).

См. также

[править | править код]

Примечания

[править | править код]
Источник — https://ru.wikipedia.org/ruwiki/w/index.php?title=Наибольшая_общая_подстрока&oldid=105610948