Самая длинная общая подстрока | ДП-29
Для двух строк «X» и «Y» найдите длину самой длинной общей подстроки.
Примеры :
Input : X = “GeeksforGeeks”, y = “GeeksQuiz”
Output : 5
Explanation:
The longest common substring is “Geeks” and is of length 5.Input : X = “abcdxyz”, y = “xyzabcd”
Output : 4
Explanation:
The longest common substring is “abcd” and is of length 4.Input : X = “zxabcdezy”, y = “yzabcdezx”
Output : 6
Explanation:
The longest common substring is “abcdez” and is of length 6.
Подход:
Пусть m и n - длины первой и второй строк соответственно.
Простое решение состоит в том, чтобы поочередно рассмотреть все подстроки первой строки и для каждой подстроки проверить, является ли она подстрокой во второй строке. Следите за подстрокой максимальной длины. Будет O (m ^ 2) подстрок, и мы сможем определить, является ли строка подстрокой в другой строке за время O (n) (см. Это). Таким образом, общая временная сложность этого метода будет O (n * m 2 )
Динамическое программирование можно использовать для поиска самой длинной общей подстроки за время O (m * n). Идея состоит в том, чтобы найти длину самого длинного общего суффикса для всех подстрок обеих строк и сохранить эти длины в таблице.
The longest common suffix has following optimal substructure property.
If last characters match, then we reduce both lengths by 1
LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
If last characters do not match, then result is 0, i.e.,
LCSuff(X, Y, m, n) = 0 if (X[m-1] != Y[n-1])
Now we consider suffixes of different substrings ending at different indexes.
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m and 1 <= j <= n
Following is the iterative implementation of the above solution.
C++
/* Dynamic Programming solution to find length of the longest common substring */#include <iostream>#include <string.h>using namespace std;/* Returns length of longest common substring of X[0..m-1] and Y[0..n-1] */int LCSubStr(char* X, char* Y, int m, int n){ // Create a table to store // lengths of longest // common suffixes of substrings. // Note that LCSuff[i][j] contains // length of longest common suffix // of X[0..i-1] and Y[0..j-1]. int LCSuff[m + 1][n + 1]; int result = 0; // To store length of the // longest common substring /* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */ for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { // The first row and first column // entries have no logical meaning, // they are used only for simplicity // of program if (i == 0 || j == 0) LCSuff[i][j] = 0; else if (X[i - 1] == Y[j - 1]) { LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1; result = max(result, LCSuff[i][j]); } else LCSuff[i][j] = 0; } } return result;}// Driver codeint main(){ char X[] = "OldSite:GeeksforGeeks.org"; char Y[] = "NewSite:GeeksQuiz.com"; int m = strlen(X); int n = strlen(Y); cout << "Length of Longest Common Substring is " << LCSubStr(X, Y, m, n); return 0;} |
Java
// Java implementation of// finding length of longest// Common substring using// Dynamic Programmingclass GFG { /* Returns length of longest common substring of X[0..m-1] and Y[0..n-1] */ static int LCSubStr(char X[], char Y[], int m, int n) { // Create a table to store // lengths of longest common // suffixes of substrings. // Note that LCSuff[i][j] // contains length of longest // common suffix of // X[0..i-1] and Y[0..j-1]. // The first row and first // column entries have no // logical meaning, they are // used only for simplicity of program int LCStuff[][] = new int[m + 1][n + 1]; // To store length of the longest // common substring int result = 0; // Following steps build // LCSuff[m+1][n+1] in bottom up fashion for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) LCStuff[i][j] = 0; else if (X[i - 1] == Y[j - 1]) { LCStuff[i][j] = LCStuff[i - 1][j - 1] + 1; result = Integer.max(result, LCStuff[i][j]); } else LCStuff[i][j] = 0; } } return result; } // Driver Code public static void main(String[] args) { String X = "OldSite:GeeksforGeeks.org"; String Y = "NewSite:GeeksQuiz.com"; int m = X.length(); int n = Y.length(); System.out.println(LCSubStr(X.toCharArray(), Y.toCharArray(), m, n)); }}// This code is contributed by Sumit Ghosh |
Python3
# Python3 implementation of Finding# Length of Longest Common Substring# Returns length of longest common# substring of X[0..m-1] and Y[0..n-1]def LCSubStr(X, Y, m, n): # Create a table to store lengths of # longest common suffixes of substrings. # Note that LCSuff[i][j] contains the # length of longest common suffix of # X[0...i-1] and Y[0...j-1]. The first # row and first column entries have no # logical meaning, they are used only # for simplicity of the program. # LCSuff is the table with zero # value initially in each cell LCSuff = [[0 for k in range(n+1)] for l in range(m+1)] # To store the length of # longest common substring result = 0 # Following steps to build # LCSuff[m+1][n+1] in bottom up fashion for i in range(m + 1): for j in range(n + 1): if (i == 0 or j == 0): LCSuff[i][j] = 0 elif (X[i-1] == Y[j-1]): LCSuff[i][j] = LCSuff[i-1][j-1] + 1 result = max(result, LCSuff[i][j]) else: LCSuff[i][j] = 0 return result# Driver CodeX = "OldSite:GeeksforGeeks.org"Y = "NewSite:GeeksQuiz.com"m = len(X)n = len(Y)print("Length of Longest Common Substring is", LCSubStr(X, Y, m, n))# This code is contributed by Soumen Ghosh |
C#
// C# implementation of finding length of longest// Common substring using Dynamic Programmingusing System;class GFG { // Returns length of longest common // substring of X[0..m-1] and Y[0..n-1] static int LCSubStr(string X, string Y, int m, int n) { // Create a table to store lengths of // longest common suffixes of substrings. // Note that LCSuff[i][j] contains length // of longest common suffix of X[0..i-1] // and Y[0..j-1]. The first row and first // column entries have no logical meaning, // they are used only for simplicity of // program int[, ] LCStuff = new int[m + 1, n + 1]; // To store length of the longest common // substring int result = 0; // Following steps build LCSuff[m+1][n+1] // in bottom up fashion for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) LCStuff[i, j] = 0; else if (X[i - 1] == Y[j - 1]) { LCStuff[i, j] = LCStuff[i - 1, j - 1] + 1; result = Math.Max(result, LCStuff[i, j]); } else LCStuff[i, j] = 0; } } return result; } // Driver Code public static void Main() { String X = "OldSite:GeeksforGeeks.org"; String Y = "NewSite:GeeksQuiz.com"; int m = X.Length; int n = Y.Length; Console.Write("Length of Longest Common" + " Substring is " + LCSubStr(X, Y, m, n)); }}// This code is contributed by Sam007. |
PHP
<?php// Dynamic Programming solution to find// length of the longest common substring// Returns length of longest common// substring of X[0..m-1] and Y[0..n-1]function LCSubStr($X, $Y, $m, $n){ // Create a table to store lengths of // longest common suffixes of substrings. // Notethat LCSuff[i][j] contains length // of longest common suffix of X[0..i-1] // and Y[0..j-1]. The first row and // first column entries have no logical // meaning, they are used only for // simplicity of program $LCSuff = array_fill(0, $m + 1, array_fill(0, $n + 1, NULL)); $result = 0; // To store length of the // longest common substring // Following steps build LCSuff[m+1][n+1] // in bottom up fashion. for ($i = 0; $i <= $m; $i++) { for ($j = 0; $j <= $n; $j++) { if ($i == 0 || $j == 0) $LCSuff[$i][$j] = 0; else if ($X[$i - 1] == $Y[$j - 1]) { $LCSuff[$i][$j] = $LCSuff[$i - 1][$j - 1] + 1; $result = max($result, $LCSuff[$i][$j]); } else $LCSuff[$i][$j] = 0; } } return $result;}// Driver Code$X = "OldSite:GeeksforGeeks.org";$Y = "NewSite:GeeksQuiz.com";$m = strlen($X);$n = strlen($Y);echo "Length of Longest Common Substring is " . LCSubStr($X, $Y, $m, $n); // This code is contributed by ita_c?> |
Length of Longest Common Substring is 10
Сложность времени: O (m * n)
Вспомогательное пространство: O (m * n)
Другой подход: (Оптимизированный по пространству подход).
В вышеупомянутом подходе мы используем только последнюю строку двумерного массива, поэтому мы можем оптимизировать пространство, используя
двумерный массив размерности 2 * (min (n, m)).
Ниже представлена реализация описанного выше подхода:
Сложность времени: O (n * m)
Вспомогательное пространство: O (min (m, n))
Another approach: (Using recursion)
Here is the recursive solution of above approach.
C++
// C++ program using to find length of the// longest common substring recursion#include <iostream>using namespace std;string X, Y;// Returns length of function f// or longest common substring// of X[0..m-1] and Y[0..n-1]int lcs(int i, int j, int count){ if (i == 0 || j == 0) return count; if (X[i - 1] == Y[j - 1]) { count = lcs(i - 1, j - 1, count + 1); } count = max(count, max(lcs(i, j - 1, 0), lcs(i - 1, j, 0))); return count;}// Driver codeint main(){ int n, m; X = "abcdxyz"; Y = "xyzabcd"; n = X.size(); m = Y.size();РЕКОМЕНДУЕМЫЕ СТАТЬИ |