Ya no tienes que indagar más por otras páginas ya que has llegado al espacio necesario, tenemos la solución que necesitas pero sin problema.
Solución:
Simplemente generalice la relación de recurrencia.
Para tres cuerdas:
dp[i, j, k] = 1 + dp[i - 1, j - 1, k - 1] if A[i] = B[j] = C[k]
max(dp[i - 1, j, k], dp[i, j - 1, k], dp[i, j, k - 1]) otherwise
Debería ser fácil de generalizar a más cadenas de este.
Solo tenía que hacer esto como tarea, así que aquí está mi solución de programación dinámica en Python que es bastante eficiente. Es O (nml) donde n, my l son las longitudes de las tres secuencias.
La solución funciona creando un 3D array y luego enumerar las tres secuencias para calcular la ruta de la subsecuencia más larga. Entonces puedes retroceder a través del array para reconstruir la subsecuencia real a partir de su ruta.
Entonces, inicializas el array a todos ceros, y luego enumere las tres secuencias. En cada paso de la enumeración, agrega uno a la longitud de la subsecuencia más larga (si hay una coincidencia) o simplemente transfiere la subsecuencia más larga del paso anterior de la enumeración.
Una vez que se completa la enumeración, ahora puede rastrear a través de la array para reconstruir la subsecuencia de los pasos que siguió. es decir, a medida que viaja hacia atrás desde la última entrada en el array, cada vez que encuentres una coincidencia, la buscas en cualquiera de las secuencias (usando la coordenada del array) y agregarlo a la subsecuencia.
def lcs3(a, b, c):
m = len(a)
l = len(b)
n = len(c)
subs = [[[0 for k in range(n+1)] for j in range(l+1)] for i in range(m+1)]
for i, x in enumerate(a):
for j, y in enumerate(b):
for k, z in enumerate(c):
if x == y and y == z:
subs[i+1][j+1][k+1] = subs[i][j][k] + 1
else:
subs[i+1][j+1][k+1] = max(subs[i+1][j+1][k],
subs[i][j+1][k+1],
subs[i+1][j][k+1])
# return subs[-1][-1][-1] #if you only need the length of the lcs
lcs = ""
while m > 0 and l > 0 and n > 0:
step = subs[m][l][n]
if step == subs[m-1][l][n]:
m -= 1
elif step == subs[m][l-1][n]:
l -= 1
elif step == subs[m][l][n-1]:
n -= 1
else:
lcs += str(a[m-1])
m -= 1
l -= 1
n -= 1
return lcs[::-1]
Para encontrar la subsecuencia común más larga (LCS) de 2 cadenas A y B, puede atravesar una array diagonalmente como se muestra en el enlace que publicó. Cada elemento del array corresponde al problema de encontrar el LCS de las subcadenas A ‘y B’ (A cortado por su número de fila, B cortado por su número de columna). Este problema se puede resolver calculando el valor de todos los elementos en el array. Debe estar seguro de que cuando calcule el valor de un array elemento, todos los subproblemas necesarios para calcular ese valor dado ya se han resuelto. Es por eso que atraviesas el bidimensional array diagonalmente.
Esta solución se puede escalar para encontrar la subsecuencia común más larga entre N cadenas, pero esto requiere una forma general de iterar una array de N dimensiones tales que cualquier elemento se alcanza solo cuando se han resuelto todos los subproblemas para los que el elemento requiere una solución.
En lugar de iterar el N-dimensional array en un orden especial, también puede resolver el problema de forma recursiva. Con la recursividad es importante guardar las soluciones intermedias, ya que muchas ramas requerirán las mismas soluciones intermedias. He escrito un pequeño ejemplo en C # que hace esto:
string lcs(string[] strings)
if (strings.Length == 0)
return "";
if (strings.Length == 1)
return strings[0];
int max = -1;
int cacheSize = 1;
for (int i = 0; i < strings.Length; i++)
cacheSize *= strings[i].Length;
if (strings[i].Length > max)
max = strings[i].Length;
string[] cache = new string[cacheSize];
int[] indexes = new int[strings.Length];
for (int i = 0; i < indexes.Length; i++)
indexes[i] = strings[i].Length - 1;
return lcsBack(strings, indexes, cache);
string lcsBack(string[] strings, int[] indexes, string[] cache)
for (int i = 0; i < indexes.Length; i++ )
if (indexes[i] == -1)
return "";
bool match = true;
for (int i = 1; i < indexes.Length; i++)
if (strings[0][indexes[0]] != strings[i][indexes[i]])
match = false;
break;
if (match)
int[] newIndexes = new int[indexes.Length];
for (int i = 0; i < indexes.Length; i++)
newIndexes[i] = indexes[i] - 1;
string result = lcsBack(strings, newIndexes, cache) + strings[0][indexes[0]];
cache[calcCachePos(indexes, strings)] = result;
return result;
else
string[] subStrings = new string[strings.Length];
for (int i = 0; i < strings.Length; i++)
if (indexes[i] <= 0)
subStrings[i] = "";
else
int[] newIndexes = new int[indexes.Length];
for (int j = 0; j < indexes.Length; j++)
newIndexes[j] = indexes[j];
newIndexes[i]--;
int cachePos = calcCachePos(newIndexes, strings);
if (cache[cachePos] == null)
subStrings[i] = lcsBack(strings, newIndexes, cache);
else
subStrings[i] = cache[cachePos];
string longestString = "";
int longestLength = 0;
for (int i = 0; i < subStrings.Length; i++)
if (subStrings[i].Length > longestLength)
longestString = subStrings[i];
longestLength = longestString.Length;
cache[calcCachePos(indexes, strings)] = longestString;
return longestString;
int calcCachePos(int[] indexes, string[] strings)
int factor = 1;
int pos = 0;
for (int i = 0; i < indexes.Length; i++)
pos += indexes[i] * factor;
factor *= strings[i].Length;
return pos;
Mi ejemplo de código se puede optimizar aún más. Muchas de las cadenas que se almacenan en caché son duplicadas y algunas son duplicadas con solo un carácter adicional agregado. Esto usa más espacio del necesario cuando las cadenas de entrada se vuelven grandes.
En la entrada: "666222054263314443712", "5432127413542377777", "6664664565464057425"
El LCS devuelto es "54442"
Aquí puedes ver las reseñas y valoraciones de los usuarios
Nos puedes añadir valor a nuestra información cooperando tu veteranía en los comentarios.