- Наибольшая общая подстрока
-
Наибольшая общая подстрока (англ. 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 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; }
Реализация на 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 []
Алгоритм, использующий суффиксное дерево
См. также
Категория:- Строковые алгоритмы
Wikimedia Foundation. 2010.