Se le dan dos strings. ¿Ahora tiene que imprimir todas las subsecuencias comunes más largas en orden lexicográfico?
Ejemplos:
Input : str1 = "abcabcaa", str2 = "acbacba"
Output: ababa
abaca
abcba
acaba
acaca
acbaa
acbca
Este problema es una extensión de la subsecuencia común más larga . Primero encontramos la longitud de LCS y almacenamos todos los LCS en una tabla 2D usando Memoización (o Programación Dinámica). Luego buscamos todos los caracteres de ‘a’ a ‘z’ (para mostrar el orden ordenado) en ambas strings. Si se encuentra un carácter en ambas strings y las posiciones actuales del carácter conducen a LCS, buscamos recursivamente todas las apariciones con la longitud actual de LCS más 1.
A continuación se muestra la implementación del algoritmo.
C++
// C++ program to find all LCS of two strings in
// sorted order.
#include<bits/stdc++.h>
#define MAX 100
using namespace std;
// length of lcs
int lcslen = 0;
// dp matrix to store result of sub calls for lcs
int dp[MAX][MAX];
// A memoization based function that returns LCS of
// str1[i..len1-1] and str2[j..len2-1]
int lcs(string str1, string str2, int len1, int len2,
int i, int j)
{
int &ret = dp[i][j];
// base condition
if (i==len1 || j==len2)
return ret = 0;
// if lcs has been computed
if (ret != -1)
return ret;
ret = 0;
// if characters are same return previous + 1 else
// max of two sequences after removing i'th and j'th
// char one by one
if (str1[i] == str2[j])
ret = 1 + lcs(str1, str2, len1, len2, i+1, j+1);
else
ret = max(lcs(str1, str2, len1, len2, i+1, j),
lcs(str1, str2, len1, len2, i, j+1));
return ret;
}
// Function to print all routes common sub-sequences of
// length lcslen
void printAll(string str1, string str2, int len1, int len2,
char data[], int indx1, int indx2, int currlcs)
{
// if currlcs is equal to lcslen then print it
if (currlcs == lcslen)
{
data[currlcs] = '\0';
puts(data);
return;
}
// if we are done with all the characters of both string
if (indx1==len1 || indx2==len2)
return;
// here we have to print all sub-sequences lexicographically,
// that's why we start from 'a'to'z' if this character is
// present in both of them then append it in data[] and same
// remaining part
for (char ch='a'; ch<='z'; ch++)
{
// done is a flag to tell that we have printed all the
// subsequences corresponding to current character
bool done = false;
for (int i=indx1; i<len1; i++)
{
// if character ch is present in str1 then check if
// it is present in str2
if (ch==str1[i])
{
for (int j=indx2; j<len2; j++)
{
// if ch is present in both of them and
// remaining length is equal to remaining
// lcs length then add ch in sub-sequence
if (ch==str2[j] &&
dp[i][j] == lcslen-currlcs)
{
data[currlcs] = ch;
printAll(str1, str2, len1, len2, data, i+1, j+1, currlcs+1);
done = true;
break;
}
}
}
// If we found LCS beginning with current character.
if (done)
break;
}
}
}
// This function prints all LCS of str1 and str2
// in lexicographic order.
void prinlAllLCSSorted(string str1, string str2)
{
// Find lengths of both strings
int len1 = str1.length(), len2 = str2.length();
// Find length of LCS
memset(dp, -1, sizeof(dp));
lcslen = lcs(str1, str2, len1, len2, 0, 0);
// Print all LCS using recursive backtracking
// data[] is used to store individual LCS.
char data[MAX];
printAll(str1, str2, len1, len2, data, 0, 0, 0);
}
// Driver program to run the case
int main()
{
string str1 = "abcabcaa", str2 = "acbacba";
prinlAllLCSSorted(str1, str2);
return 0;
}
Java
// Java program to find all LCS of two strings in
// sorted order.
class GFG
{
static int MAX = 100;
// length of lcs
static int lcslen = 0;
// dp matrix to store result of sub calls for lcs
static int[][] dp = new int[MAX][MAX];
// A memoization based function that returns LCS of
// str1[i..len1-1] and str2[j..len2-1]
static int lcs(String str1, String str2,
int len1, int len2, int i, int j)
{
int ret = dp[i][j];
// base condition
if (i == len1 || j == len2)
return ret = 0;
// if lcs has been computed
if (ret != -1)
return ret;
ret = 0;
// if characters are same return previous + 1 else
// max of two sequences after removing i'th and j'th
// char one by one
if (str1.charAt(i) == str2.charAt(j))
ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1);
else
ret = Math.max(lcs(str1, str2, len1, len2, i + 1, j),
lcs(str1, str2, len1, len2, i, j + 1));
return ret;
}
// Function to print all routes common sub-sequences of
// length lcslen
static void printAll(String str1, String str2, int len1, int len2,
char[] data, int indx1, int indx2, int currlcs)
{
// if currlcs is equal to lcslen then print it
if (currlcs == lcslen)
{
data[currlcs] = '\0';
System.out.println(new String(data));
return;
}
// if we are done with all the characters of both string
if (indx1 == len1 || indx2 == len2)
return;
// here we have to print all sub-sequences lexicographically,
// that's why we start from 'a'to'z' if this character is
// present in both of them then append it in data[] and same
// remaining part
for (char ch ='a'; ch <='z'; ch++)
{
// done is a flag to tell that we have printed all the
// subsequences corresponding to current character
boolean done = false;
for (int i = indx1; i < len1; i++)
{
// if character ch is present in str1 then check if
// it is present in str2
if (ch == str1.charAt(i))
{
for (int j = indx2; j < len2; j++)
{
// if ch is present in both of them and
// remaining length is equal to remaining
// lcs length then add ch in sub-sequence
if (ch == str2.charAt(j) &&
dp[i][j] == lcslen - currlcs)
{
data[currlcs] = ch;
printAll(str1, str2, len1, len2,
data, i + 1, j + 1, currlcs + 1);
done = true;
break;
}
}
}
// If we found LCS beginning with current character.
if (done)
break;
}
}
}
// This function prints all LCS of str1 and str2
// in lexicographic order.
static void prinlAllLCSSorted(String str1, String str2)
{
// Find lengths of both strings
int len1 = str1.length(), len2 = str2.length();
// Find length of LCS
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
lcslen = lcs(str1, str2, len1, len2, 0, 0);
// Print all LCS using recursive backtracking
// data[] is used to store individual LCS.
char[] data = new char[MAX];
printAll(str1, str2, len1, len2, data, 0, 0, 0);
}
// Driver code
public static void main(String[] args)
{
String str1 = "abcabcaa", str2 = "acbacba";
prinlAllLCSSorted(str1, str2);
}
}
// This code is contributed by divyesh072019
Python3
# Python3 program to find all LCS of two strings in
# sorted order.
MAX=100
lcslen = 0
# dp matrix to store result of sub calls for lcs
dp=[[-1 for i in range(MAX)] for i in range(MAX)]
# A memoization based function that returns LCS of
# str1[i..len1-1] and str2[j..len2-1]
def lcs(str1, str2, len1, len2, i, j):
# base condition
if (i == len1 or j == len2):
dp[i][j] = 0
return dp[i][j]
# if lcs has been computed
if (dp[i][j] != -1):
return dp[i][j]
ret = 0
# if characters are same return previous + 1 else
# max of two sequences after removing i'th and j'th
# char one by one
if (str1[i] == str2[j]):
ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1)
else:
ret = max(lcs(str1, str2, len1, len2, i + 1, j),
lcs(str1, str2, len1, len2, i, j + 1))
dp[i][j] = ret
return ret
# Function to print all routes common sub-sequences of
# length lcslen
def printAll(str1, str2, len1, len2,data, indx1, indx2, currlcs):
# if currlcs is equal to lcslen then print
if (currlcs == lcslen):
print("".join(data[:currlcs]))
return
# if we are done with all the characters of both string
if (indx1 == len1 or indx2 == len2):
return
# here we have to print all sub-sequences lexicographically,
# that's why we start from 'a'to'z' if this character is
# present in both of them then append it in data[] and same
# remaining part
for ch in range(ord('a'),ord('z') + 1):
# done is a flag to tell that we have printed all the
# subsequences corresponding to current character
done = False
for i in range(indx1,len1):
# if character ch is present in str1 then check if
# it is present in str2
if (chr(ch)==str1[i]):
for j in range(indx2, len2):
# if ch is present in both of them and
# remaining length is equal to remaining
# lcs length then add ch in sub-sequence
if (chr(ch) == str2[j] and dp[i][j] == lcslen-currlcs):
data[currlcs] = chr(ch)
printAll(str1, str2, len1, len2, data, i + 1, j + 1, currlcs + 1)
done = True
break
# If we found LCS beginning with current character.
if (done):
break
# This function prints all LCS of str1 and str2
# in lexicographic order.
def prinlAllLCSSorted(str1, str2):
global lcslen
# Find lengths of both strings
len1,len2 = len(str1),len(str2)
lcslen = lcs(str1, str2, len1, len2, 0, 0)
# Print all LCS using recursive backtracking
# data[] is used to store individual LCS.
data = ['a' for i in range(MAX)]
printAll(str1, str2, len1, len2, data, 0, 0, 0)
# Driver program to run the case
if __name__ == '__main__':
str1 = "abcabcaa"
str2 = "acbacba"
prinlAllLCSSorted(str1, str2)
# This code is contributed by mohit kumar 29
C#
// C# program to find all LCS of two strings in
// sorted order.
using System;
class GFG
{
static int MAX = 100;
// length of lcs
static int lcslen = 0;
// dp matrix to store result of sub calls for lcs
static int[,] dp = new int[MAX,MAX];
// A memoization based function that returns LCS of
// str1[i..len1-1] and str2[j..len2-1]
static int lcs(string str1, string str2,
int len1, int len2, int i, int j)
{
int ret = dp[i, j];
// base condition
if (i == len1 || j == len2)
return ret = 0;
// if lcs has been computed
if (ret != -1)
return ret;
ret = 0;
// if characters are same return previous + 1 else
// max of two sequences after removing i'th and j'th
// char one by one
if (str1[i] == str2[j])
ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1);
else
ret = Math.Max(lcs(str1, str2, len1, len2, i + 1, j),
lcs(str1, str2, len1, len2, i, j + 1));
return ret;
}
// Function to print all routes common sub-sequences of
// length lcslen
static void printAll(string str1, string str2, int len1, int len2,
char[] data, int indx1, int indx2, int currlcs)
{
// if currlcs is equal to lcslen then print it
if (currlcs == lcslen)
{
data[currlcs] = '\0';
Console.WriteLine(new string(data));
return;
}
// if we are done with all the characters of both string
if (indx1 == len1 || indx2 == len2)
return;
// here we have to print all sub-sequences lexicographically,
// that's why we start from 'a'to'z' if this character is
// present in both of them then append it in data[] and same
// remaining part
for (char ch='a'; ch<='z'; ch++)
{
// done is a flag to tell that we have printed all the
// subsequences corresponding to current character
bool done = false;
for (int i = indx1; i < len1; i++)
{
// if character ch is present in str1 then check if
// it is present in str2
if (ch == str1[i])
{
for (int j = indx2; j < len2; j++)
{
// if ch is present in both of them and
// remaining length is equal to remaining
// lcs length then add ch in sub-sequence
if (ch == str2[j] &&
lcs(str1, str2, len1, len2, i, j) == lcslen-currlcs)
{
data[currlcs] = ch;
printAll(str1, str2, len1, len2, data, i+1, j+1, currlcs+1);
done = true;
break;
}
}
}
// If we found LCS beginning with current character.
if (done)
break;
}
}
}
// This function prints all LCS of str1 and str2
// in lexicographic order.
static void prinlAllLCSSorted(string str1, string str2)
{
// Find lengths of both strings
int len1 = str1.Length, len2 = str2.Length;
// Find length of LCS
for(int i = 0; i < MAX; i++)
{
for(int j = 0; j < MAX; j++)
{
dp[i, j] = -1;
}
}
lcslen = lcs(str1, str2, len1, len2, 0, 0);
// Print all LCS using recursive backtracking
// data[] is used to store individual LCS.
char[] data = new char[MAX];
printAll(str1, str2, len1, len2, data, 0, 0, 0);
}
// Driver code
static void Main()
{
string str1 = "abcabcaa", str2 = "acbacba";
prinlAllLCSSorted(str1, str2);
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program to find all LCS of two strings in
// sorted order.
let MAX = 100;
// length of lcs
let lcslen = 0;
// dp matrix to store result of sub calls for lcs
let dp = new Array(MAX);
// A memoization based function that returns LCS of
// str1[i..len1-1] and str2[j..len2-1]
function lcs(str1,str2,len1,len2,i,j)
{
let ret = dp[i][j];
// base condition
if (i == len1 || j == len2)
return ret = 0;
// if lcs has been computed
if (ret != -1)
return ret;
ret = 0;
// if characters are same return previous + 1 else
// max of two sequences after removing i'th and j'th
// char one by one
if (str1[i] == str2[j])
ret = 1 + lcs(str1, str2, len1, len2, i + 1, j + 1);
else
ret = Math.max(lcs(str1, str2, len1, len2, i + 1, j),
lcs(str1, str2, len1, len2, i, j + 1));
return ret;
}
// Function to print all routes common sub-sequences of
// length lcslen
function printAll(str1,str2,len1,len2,data,indx1,indx2,currlcs)
{
// if currlcs is equal to lcslen then print it
if (currlcs == lcslen)
{
data[currlcs] = null;
document.write(data.join("")+"<br>");
return;
}
// if we are done with all the characters of both string
if (indx1 == len1 || indx2 == len2)
return;
// here we have to print all sub-sequences lexicographically,
// that's why we start from 'a'to'z' if this character is
// present in both of them then append it in data[] and same
// remaining part
for (let ch ='a'.charCodeAt(0); ch <='z'.charCodeAt(0); ch++)
{
// done is a flag to tell that we have printed all the
// subsequences corresponding to current character
let done = false;
for (let i = indx1; i < len1; i++)
{
// if character ch is present in str1 then check if
// it is present in str2
if (ch == str1[i].charCodeAt(0))
{
for (let j = indx2; j < len2; j++)
{
// if ch is present in both of them and
// remaining length is equal to remaining
// lcs length then add ch in sub-sequence
if (ch == str2[j].charCodeAt(0) &&
lcs(str1, str2, len1, len2, i, j) == lcslen - currlcs)
{
data[currlcs] = String.fromCharCode(ch);
printAll(str1, str2, len1, len2,
data, i + 1, j + 1, currlcs + 1);
done = true;
break;
}
}
}
// If we found LCS beginning with current character.
if (done)
break;
}
}
}
// This function prints all LCS of str1 and str2
// in lexicographic order.
function prinlAllLCSSorted(str1,str2)
{
// Find lengths of both strings
let len1 = str1.length, len2 = str2.length;
// Find length of LCS
for(let i = 0; i < MAX; i++)
{
dp[i]=new Array(MAX);
for(let j = 0; j < MAX; j++)
{
dp[i][j] = -1;
}
}
lcslen = lcs(str1, str2, len1, len2, 0, 0);
// Print all LCS using recursive backtracking
// data[] is used to store individual LCS.
let data = new Array(MAX);
printAll(str1, str2, len1, len2, data, 0, 0, 0);
}
// Driver code
let str1 = "abcabcaa", str2 = "acbacba";
prinlAllLCSSorted(str1, str2);
// This code is contributed by unknown2108
</script>
Producción
ababa abaca abcba acaba acaca acbaa acbca
Complejidad de tiempo: O(m*n*p) , donde ‘m’ es la longitud de la array de caracteres, ‘n’ es la longitud de la array1 y ‘p’ es la longitud de la array2.
Este artículo es una contribución de Shashak Mishra (Gullu) . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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