Наибольшая общая подстрока
Наибольшая общая подстрока (англ. 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).
Реализация на C++
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);
}
Реализация на C#
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;
}
Реализация на C# (вариант)
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]);
}
Реализация на 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 []
Реализация на 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)