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

[непроверенная версия]

[отпатрулированная версия]

Содержимое удалено Содержимое добавлено

Линейный

Версия от 03:12, 23 марта 2018

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

В таблице заполнены значения для строк 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).

См. также

Примечания

@@ Строка 3: / Строка 3: @@
 Формально, наибольшей общей [[Подстрока|подстрокой]] строк <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> по следующему правилу, принимая, что символы в строке нумеруются от единицы.
@@ Строка 35: / Строка 33: @@
  '''S''' 0'''1'''00'''1'''0000000
- Получаем наибольшую общую подстроку '''UENC'''
+Получаем наибольшую общую подстроку '''UENC'''
 Очевидно, сложность такого алгоритма составляет ''[[«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>
-==== Реализация на Java ====
-<source lang="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);
-}</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>
-==== Реализация на Ruby<ref>{{Cite web|url=http://stackoverflow.com/a/2158481/5713602|title=Finding common string in array of strings (ruby)|publisher=stackoverflow.com|accessdate=2016-03-30}}</ref> ====
-<source lang="ruby">
-def longest_common_substr(strings)
-  shortest = strings.min_by &:length
-  maxlen = shortest.length
-  maxlen.downto(0) do |len|
-.upto(maxlen - len) do |start|
-      substr = shortest[start,len]
-      return substr if strings.all?{|str| str.include? substr }
-    end
-  end
-end
-</source>
-Но нужно отметить, что код не реализует приведенный в статье алгоритм динамического программирования. Это рабочая реализация для поиска наибольшей общей подстроки для произвольного количества строк, но она написана в стиле скриптового языка, простым перебором.
-=== Алгоритм, использующий [[суффиксное дерево]] ===
 == См. также ==

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

Версия от 03:12, 23 марта 2018

См. также

Примечания

Навигация

Поиск