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

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

Формально, наибольшей общей подстрокой строк $s_{1},s_{2},\ldots s_{n}$ называется строка $\left.w^{*}\right.$, которая удовлетворяет условию $\|w^{*}\|=\max(\{\|w\||w\sqsubseteq s_{i},i=1,\ldots n\})$, операция $w\sqsubseteq s_{i}$ обозначает что строка $\left.w\right.$ является (возможно несобственной) подстрокой строки $\left.s_{i}\right.$.

Алгоритмы поиска наибольшей общей подстроки

Наивный алгоритм

Решение задачи поиска наибольшей общей подстроки для двух строк $\left.s_{1}\right.$ и $\left.s_{2}\right.$, длины которых $\left.m\right.$ и $\left.n\right.$ соответственно, заключается в заполнении таблицы $\left.A_{ij}\right.$ размером $(m+1)\times (n+1)$ по следующему правилу, принимая, что символы в строке нумеруются от единицы.

$\left\{{\begin{array}{rclr}A_{0j}&=&0,&j=0\ldots n,\\A_{i0}&=&0,&i=0\ldots m,\\A_{ij}&=&0,&s_{1}[i]\neq s_{2}[j],i\neq 0,j\neq 0,\\A_{ij}&=&A_{i-1j-1}+1,&s_{1}[i]=s_{2}[j],i\neq 0,j\neq 0.\end{array}}\right.$

Максимальное число $\left.A_{uv}\right.$ в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

$s_{1}[u-A_{uv}+1]\ldots s_{1}[u]$ и $s_{2}[v-A_{uv}+1]\ldots s_{2}[vu]$.

В таблице заполнены значения для строк 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 str1, string str2 )
{
   var a = new int [str1.Length + 1, str2.Length + 1];
   int u = 0,  v = 0;
  
   for (var i = 0; i < str1.Length; i++) 
      for (var j = 0; j < str2.Length; j++) 
         if (str1[i] == str2[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 str1.Substring(u - a[u,v], a[u,v]);
}

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

См. также

• Суффиксное дерево
• Алгоритмы на строках
• Наибольшая общая подпоследовательность