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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правка
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Нет описания правки
м Checkwiki #1. Исправление избыточного префикса "Шаблон:"
 
(не показано 11 промежуточных версий 11 участников)
Строка 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> по следующему правилу, принимая, что символы в строке нумеруются от единицы.


Строка 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_size = a.size();
const int b_size = b.size();

typedef vector<int> solution;

const int solution_size = b_size + 1;
solution x(solution_size, 0), y(solution_size);

solution * previous = &x;
solution * current = &y;

int max_length = 0;
int result_index = 0;

for(int i = a_size - 1; i >= 0; i--) {
for(int j = b_size - 1; j >= 0; j--) {
int & current_match = (*current)[j];
if(a[i] != b[j]) {
current_match = 0;
}
else {
const int length = 1 + (*previous)[j + 1];
if (length > max_length) {
max_length = length;
result_index = i;
}

current_match = length;
}
}

swap(previous, current);
}

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 LongestCommonSubstringLength( 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>

==== Реализация на C# (вариант) ====
<source lang="csharp">
public static string LCS (string s1, string s2)
{
var a = new int [s1.Length + 1, s2.Length + 1];
int u = 0, v = 0;
for (var i = 0; i < s1.Length; i++)
for (var j = 0; j < s2.Length; j++)
if (s1[i] == s2[j])
{
a[i + 1, j + 1] = a[i, j] + 1;
if (a[i + 1, j + 1] > a[u, v])
{
u = i + 1;
v = j + 1;
}
}
return s1.Substring(u - a[u,v], a[u,v]);
}
</source>

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

lcstr xs ys = reverse . maximumBy (comparing length) . concat $ [f xs' ys | xs' <- tails xs] ++ [f xs ys' | ys' <- tail $ tails ys]
where f xs ys = scanl g [] $ zip xs ys
g z (x, y) = if x == y then x:z else []
</source>

==== Реализация на Python ====
Первой строкой входного файла следует цифра обозначающая количество строк в которых следует искать подстроку.
Строки для поиска следуют дальше.
<source lang="Python">
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
list = sys.argv[1:]
fileName = list[0]
data = open(fileName).read().splitlines()
numOfStrings = int(data.pop(0))-1
data = filter(None, data)
data.sort(key=len)
leastStr = data.pop(0)
maxSharedStr = ''
while len(leastStr) > len(maxSharedStr):
robTestStr = leastStr
while len(robTestStr) > len(maxSharedStr):
numOfConcidence = 0
for compatStr in data:
if robTestStr in compatStr:
numOfConcidence += 1
else:
break
if numOfConcidence == numOfStrings and len(robTestStr) > len(maxSharedStr):
maxSharedStr = robTestStr
robTestStr = robTestStr[:-1]
leastStr = leastStr[1:]
print maxSharedStr
sys.exit(0)
</source>

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


== См. также ==
== См. также ==
Строка 187: Строка 41:
* [[Список алгоритмов#Алгоритмы на строках|Алгоритмы на строках]]
* [[Список алгоритмов#Алгоритмы на строках|Алгоритмы на строках]]
* [[Наибольшая общая подпоследовательность]]
* [[Наибольшая общая подпоследовательность]]

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


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

Текущая версия от 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