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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Наибольшая общая подстрока (англ. 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);
}

Реализация на Java[править | править вики-текст]

private static String longestCS(String a, String b) {
	if (a == null || b == null || a.length() == 0 || b.length() == 0) {
		return "";
	}

	if (a.equals(b)) {
		return a;
	}

	int[][] matrix = new int[a.length()][];

	int maxLength = 0;
	int maxI = 0;

	for (int i = 0; i < matrix.length; i++) {
		matrix[i] = new int[b.length()];
		for (int j = 0; j < matrix[i].length; j++) {
			if (a.charAt(i) == b.charAt(j)) {
				if (i != 0 && j != 0) {
					matrix[i][j] = matrix[i - 1][j - 1] + 1;
				} else {
					matrix[i][j] = 1;
				}
				if (matrix[i][j] > maxLength) {
					maxLength = matrix[i][j];
					maxI = i;
				}
			}
		}
	}
	return a.substring(maxI - maxLength + 1, maxI + 1);
}

Реализация на 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 []

Реализация на Ruby[1][править | править вики-текст]

def longest_common_substr(strings)
  shortest = strings.min_by &:length
  maxlen = shortest.length
  maxlen.downto(0) do |len|
    0.upto(maxlen - len) do |start|
      substr = shortest[start,len]
      return substr if strings.all?{|str| str.include? substr }
    end
  end
end

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Finding common string in array of strings (ruby). stackoverflow.com. Проверено 30 марта 2016.