Dadas dos strings ‘X’ e ‘Y’, imprima la longitud de la substring común más larga. Si dos o más substrings tienen el mismo valor para la substring común más larga, imprima cualquiera de ellas.
Ejemplos:
Input : X = "GeeksforGeeks",
Y = "GeeksQuiz"
Output : Geeks
Input : X = "zxabcdezy",
Y = "yzabcdezx"
Output : abcdez
Hemos discutido una solución para encontrar la longitud de la string común más larga. En esta publicación, hemos discutido la impresión de strings comunes.
Enfoque ingenuo: Deje que las strings X e Y sean las longitudes m y n respectivamente. Genere todas las substrings posibles de X que requieran una complejidad de tiempo de O(m 2 ) y busque cada substring en la string Y que se pueda lograr en una complejidad de tiempo O(n) utilizando el algoritmo KMP . La complejidad del tiempo total será O(n * m 2 ).
Enfoque eficiente: se basa en la implementación de programación dinámica explicada en esta publicación. Se construye la array de sufijos más larga LCSuff[][] y se rastrea el índice de la celda que tiene el valor máximo. Deje que ese índice esté representado por (fila, columna) par. Ahora, la substring común más larga final se construye con la ayuda de ese índice al atravesar diagonalmente la array LCSuff[][] hasta LCSuff[fila][col] != 0 y durante la iteración se obtienen los caracteres de X[fila-1 ] o Y[col-1] y añadiéndolos de derecha a izquierda en la string común resultante.
Implementación:
C++
// C++ implementation to print the longest common substring
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
/* function to find and print the longest common
substring of X[0..m-1] and Y[0..n-1] */
void printLCSubStr(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 LCSuff[m + 1][n + 1];
// To store length of the longest common substring
int len = 0;
// To store the index of the cell which contains the
// maximum value. This cell's index helps in building
// up the longest common substring from right to left.
int row, col;
/* 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)
LCSuff[i][j] = 0;
else if (X[i - 1] == Y[j - 1]) {
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
if (len < LCSuff[i][j]) {
len = LCSuff[i][j];
row = i;
col = j;
}
}
else
LCSuff[i][j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
cout << "No Common Substring";
return;
}
// allocate space for the longest common substring
char* resultStr = (char*)malloc((len + 1) * sizeof(char));
// traverse up diagonally form the (row, col) cell
// until LCSuff[row][col] != 0
while (LCSuff[row][col] != 0) {
resultStr[--len] = X[row - 1]; // or Y[col-1]
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
cout << resultStr;
}
/* Driver program to test above function */
int main()
{
char X[] = "OldSite:GeeksforGeeks.org";
char Y[] = "NewSite:GeeksQuiz.com";
int m = strlen(X);
int n = strlen(Y);
printLCSubStr(X, Y, m, n);
return 0;
}
Java
// Java implementation to print the longest common substring
public class Longest_common_substr {
/* function to find and print the longest common
substring of X[0..m-1] and Y[0..n-1] */
static void printLCSubStr(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[][] LCSuff = new int[m + 1][n + 1];
// To store length of the longest common substring
int len = 0;
// To store the index of the cell which contains the
// maximum value. This cell's index helps in building
// up the longest common substring from right to left.
int row = 0, col = 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)
LCSuff[i][j] = 0;
else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
if (len < LCSuff[i][j]) {
len = LCSuff[i][j];
row = i;
col = j;
}
}
else
LCSuff[i][j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
System.out.println("No Common Substring");
return;
}
// allocate space for the longest common substring
String resultStr = "";
// traverse up diagonally form the (row, col) cell
// until LCSuff[row][col] != 0
while (LCSuff[row][col] != 0) {
resultStr = X.charAt(row - 1) + resultStr; // or Y[col-1]
--len;
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
System.out.println(resultStr);
}
/* Driver program to test above function */
public static void main(String args[])
{
String X = "OldSite:GeeksforGeeks.org";
String Y = "NewSite:GeeksQuiz.com";
int m = X.length();
int n = Y.length();
printLCSubStr(X, Y, m, n);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python3 implementation to print
# the longest common substring
# function to find and print
# the longest common substring of
# X[0..m-1] and Y[0..n-1]
def printLCSSubStr(X: str, Y: str,
m: int, n: int):
# 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
LCSuff = [[0 for i in range(n + 1)]
for j in range(m + 1)]
# To store length of the
# longest common substring
length = 0
# To store the index of the cell
# which contains the maximum value.
# This cell's index helps in building
# up the longest common substring
# from right to left.
row, col = 0, 0
# Following steps 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
else if X[i - 1] == Y[j - 1]:
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1
if length < LCSuff[i][j]:
length = LCSuff[i][j]
row = i
col = j
else:
LCSuff[i][j] = 0
# if true, then no common substring exists
if length == 0:
print("No Common Substring")
return
# allocate space for the longest
# common substring
resultStr = ['0'] * length
# traverse up diagonally form the
# (row, col) cell until LCSuff[row][col] != 0
while LCSuff[row][col] != 0:
length -= 1
resultStr[length] = X[row - 1] # or Y[col-1]
# move diagonally up to previous cell
row -= 1
col -= 1
# required longest common substring
print(''.join(resultStr))
# Driver Code
if __name__ == "__main__":
X = "OldSite:GeeksforGeeks.org"
Y = "NewSite:GeeksQuiz.com"
m = len(X)
n = len(Y)
printLCSSubStr(X, Y, m, n)
# This code is contributed by
# sanjeev2552
C#
// C# implementation to print the
// longest common substring
using System;
class GFG {
/* function to find and print the longest common
substring of X[0..m-1] and Y[0..n-1] */
static void printLCSubStr(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[, ] LCSuff = new int[m + 1, n + 1];
// To store length of the longest common substring
int len = 0;
// To store the index of the cell which contains the
// maximum value. This cell's index helps in building
// up the longest common substring from right to left.
int row = 0, col = 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)
LCSuff[i, j] = 0;
else if (X[i - 1] == Y[j - 1]) {
LCSuff[i, j] = LCSuff[i - 1, j - 1] + 1;
if (len < LCSuff[i, j]) {
len = LCSuff[i, j];
row = i;
col = j;
}
}
else
LCSuff[i, j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
Console.Write("No Common Substring");
return;
}
// allocate space for the longest common substring
String resultStr = "";
// traverse up diagonally form the (row, col) cell
// until LCSuff[row][col] != 0
while (LCSuff[row, col] != 0) {
resultStr = X[row - 1] + resultStr; // or Y[col-1]
--len;
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
Console.WriteLine(resultStr);
}
/* Driver program to test above function */
public static void Main()
{
String X = "OldSite:GeeksforGeeks.org";
String Y = "NewSite:GeeksQuiz.com";
int m = X.Length;
int n = Y.Length;
printLCSubStr(X, Y, m, n);
}
}
// This code is contributed by Sam007
Javascript
<script>
// Javascript implementation to print the longest common substring
/* function to find and print the longest common
substring of X[0..m-1] and Y[0..n-1] */
function printLCSubStr(X,Y,m,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
let LCSuff = new Array(m+1);
// To store length of the longest common substring
let len = 0;
// To store the index of the cell which contains the
// maximum value. This cell's index helps in building
// up the longest common substring from right to left.
let row = 0, col = 0;
/* Following steps build LCSuff[m+1][n+1] in bottom
up fashion. */
for (let i = 0; i <= m; i++) {
LCSuff[i] = Array(n+1);
for (let j = 0; j <= n; j++) {
LCSuff[i][j]=0;
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;
if (len < LCSuff[i][j]) {
len = LCSuff[i][j];
row = i;
col = j;
}
}
else
LCSuff[i][j] = 0;
}
}
// if true, then no common substring exists
if (len == 0) {
document.write("No Common Substring");
return;
}
// allocate space for the longest common substring
let resultStr = "";
// traverse up diagonally form the (row, col) cell
// until LCSuff[row][col] != 0
while (LCSuff[row][col] != 0) {
resultStr = X[row-1] + resultStr; // or Y[col-1]
--len;
// move diagonally up to previous cell
row--;
col--;
}
// required longest common substring
document.write(resultStr);
}
/* Driver program to test above function */
let X = "OldSite:GeeksforGeeks.org";
let Y = "NewSite:GeeksQuiz.com";
let m = X.length;
let n = Y.length;
printLCSubStr(X, Y, m, n);
//This code is contributed by rag2127
</script>
Producción:
Site:Geeks
Complejidad temporal: O(m*n).
Espacio Auxiliar: O(m*n).
Enfoque de espacio optimizado: el espacio auxiliar utilizado por la solución anterior es O(m*n) , donde m y n son longitudes de string X e Y. El espacio utilizado por la solución anterior se puede reducir a O(2*n) . Se usa una variable end para almacenar el punto final de la substring común más larga en la string X y la variable maxlen se usa para almacenar la longitud de la substring común más larga.
Supongamos que estamos en el estado DP cuando la longitud de X es i y la longitud de Y es j, cuyo resultado se almacena en len[i][j].
Ahora, si X[i-1] == Y[j-1], entonces len[i][j] = 1 + len[i-1][j-1] , ese es el resultado de la fila actual en la array len[ ][] depende de los valores de la fila anterior. Por lo tanto, la longitud requerida de la substring común más larga se puede obtener manteniendo los valores de solo dos filas consecutivas, lo que reduce los requisitos de espacio a O(2*n).
Para imprimir la substring común más larga, usamos un final variable. Cuando se calcula len[i][j], se compara con maxlen. Si maxlen es menor que len[i][j], end se actualiza a i-1 para mostrar que la substring común más larga termina en el índice i-1 en X y maxlen se actualiza a len[i][j]. Entonces, la substring común más larga es desde el final del índice: maxlen + 1 hasta el final del índice en X.
Se usa una variable currRow para representar que la fila 0 o la fila 1 de la array len[2][n] se usa actualmente para encontrar la longitud. Inicialmente, la fila 0 se usa como la fila actual para el caso en que la longitud de la string X sea cero. Al final de cada iteración, la fila actual se convierte en la fila anterior y la fila anterior se convierte en la nueva fila actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// Space optimized CPP implementation to print
// longest common substring.
#include <bits/stdc++.h>
using namespace std;
// Function to find longest common substring.
string LCSubStr(string X, string Y)
{
// Find length of both the strings.
int m = X.length();
int n = Y.length();
// Variable to store length of longest
// common substring.
int result = 0;
// Variable to store ending point of
// longest common substring in X.
int end;
// Matrix to store result of two
// consecutive rows at a time.
int len[2][n + 1];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common substring in string X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
}
else if (X[i - 1] == Y[j - 1]) {
len[currRow][j] = len[1 - currRow][j - 1] + 1;
if (len[currRow][j] > result) {
result = len[currRow][j];
end = i - 1;
}
}
else {
len[currRow][j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currRow = 1 - currRow;
}
// If there is no common substring, print -1.
if (result == 0) {
return "-1";
}
// Longest common substring is from index
// end - result + 1 to index end in X.
return X.substr(end - result + 1, result);
}
// Driver Code
int main()
{
string X = "GeeksforGeeks";
string Y = "GeeksQuiz";
// function call
cout << LCSubStr(X, Y);
return 0;
}
Java
// Space optimized Java implementation to print
// longest common substring.
public class GFG {
// Function to find longest common substring.
static String LCSubStr(String X, String Y) {
// Find length of both the Strings.
int m = X.length();
int n = Y.length();
// Variable to store length of longest
// common subString.
int result = 0;
// Variable to store ending point of
// longest common subString in X.
int end = 0;
// Matrix to store result of two
// consecutive rows at a time.
int len[][] = new int[2][m];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common subString in String X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
len[currRow][j] = len[1 - currRow][j - 1] + 1;
if (len[currRow][j] > result) {
result = len[currRow][j];
end = i - 1;
}
} else {
len[currRow][j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currRow = 1 - currRow;
}
// If there is no common subString, print -1.
if (result == 0) {
return "-1";
}
// Longest common subString is from index
// end - result + 1 to index end in X.
return X.substring(end - result + 1, result);
}
// Driver Code
public static void main(String[] args) {
String X = "GeeksforGeeks";
String Y = "GeeksQuiz";
// function call
System.out.println(LCSubStr(X, Y));
}
}
// This code is contributed by PrinciRaj1992
Python3
# Space optimized Python3 implementation to # print longest common substring. # Function to find longest common substring. def LCSubStr(X, Y): # Find length of both the strings. m = len(X) n = len(Y) # Variable to store length of longest # common substring. result = 0 # Variable to store ending point of # longest common substring in X. end = 0 # Matrix to store result of two # consecutive rows at a time. length = [[0 for j in range(m)] for i in range(2)] # Variable to represent which row of # matrix is current row. currRow = 0 # For a particular value of i and j, # length[currRow][j] stores length # of longest common substring in # string X[0..i] and Y[0..j]. for i in range(0, m + 1): for j in range(0, n + 1): if (i == 0 or j == 0): length[currRow][j] = 0 elif (X[i - 1] == Y[j - 1]): length[currRow][j] = length[1 - currRow][j - 1] + 1 if (length[currRow][j] > result): result = length[currRow][j] end = i - 1 else: length[currRow][j] = 0 # Make current row as previous row and # previous row as new current row. currRow = 1 - currRow # If there is no common substring, print -1. if (result == 0): return "-1" # Longest common substring is from index # end - result + 1 to index end in X. return X[end - result + 1 : end + 1] # Driver code if __name__=="__main__": X = "GeeksforGeeks" Y = "GeeksQuiz" # Function call print(LCSubStr(X, Y)) # This code is contributed by rutvik_56
C#
using System;
// Space optimized Java implementation to print
// longest common substring.
public class GFG {
// Function to find longest common substring.
static string LCSubStr(string X, string Y) {
// Find length of both the Strings.
int m = X.Length;
int n = Y.Length;
// Variable to store length of longest
// common subString.
int result = 0;
// Variable to store ending point of
// longest common subString in X.
int end = 0;
// Matrix to store result of two
// consecutive rows at a time.
int[,] len = new int[2,m];
// Variable to represent which row of
// matrix is current row.
int currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common subString in String X[0..i] and Y[0..j].
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow,j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
len[currRow,j] = len[1 - currRow,j - 1] + 1;
if (len[currRow,j] > result) {
result = len[currRow,j];
end = i - 1;
}
} else {
len[currRow,j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currRow = 1 - currRow;
}
// If there is no common subString, print -1.
if (result == 0) {
return "-1";
}
// Longest common subString is from index
// end - result + 1 to index end in X.
return X.Substring(end - result + 1, result);
}
// Driver Code
public static void Main() {
string X = "GeeksforGeeks";
string Y = "GeeksQuiz";
// function call
Console.Write(LCSubStr(X, Y));
}
}
Javascript
<script>
// Space optimized javascript implementation to print
// longest common substring.
// Function to find longest common substring.
function LCSubStr(X,Y)
{
// Find length of both the strings.
let m = X.length;
let n = Y.length;
// Variable to store length of longest
// common substring.
let result = 0;
// Variable to store ending point of
// longest common substring in X.
let end;
// Matrix to store result of two
// consecutive rows at a time.
let len= new Array(2);
for(let i=0;i<len.length;i++)
{
len[i]=new Array(n);
for(let j=0;j<n;j++)
{
len[i][j]=0;
}
}
// Variable to represent which row of
// matrix is current row.
let currRow = 0;
// For a particular value of i and j,
// len[currRow][j] stores length of longest
// common substring in string X[0..i] and Y[0..j].
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
len[currRow][j] = 0;
}
else if (X[i - 1] == Y[j - 1]) {
len[currRow][j] = len[1 - currRow][j - 1] + 1;
if (len[currRow][j] > result) {
result = len[currRow][j];
end = i - 1;
}
}
else {
len[currRow][j] = 0;
}
}
// Make current row as previous row and
// previous row as new current row.
currRow = 1 - currRow;
}
// If there is no common substring, print -1.
if (result == 0) {
return "-1";
}
// Longest common substring is from index
// end - result + 1 to index end in X.
return X.substr(end - result + 1, result);
}
// Driver Code
let X = "GeeksforGeeks";
let Y = "GeeksQuiz";
// function call
document.write(LCSubStr(X, Y));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
Geeks
Tiempo Complejidad: O(m*n)
Espacio Auxiliar: O(n)
Este enfoque ha sido sugerido por nik1996.
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA