subsecuencia mas manejo libreria larga funciones ejemplos declarar creciente comun caracteres cadenas cadena c++ algorithm lcs

c++ - manejo - subsecuencia comun mas larga java



Cómo encontrar la subcadena común más larga usando C++ (7)

Busqué en línea una implementación de Substring común más larga de C ++ pero no encontré una decente. Necesito un algoritmo LCS que devuelva la subcadena, así que no es solo LCS.

Me preguntaba, sin embargo, sobre cómo puedo hacer esto entre varias cadenas.

Mi idea fue verificar la más larga entre 2 cadenas y luego revisar todas las demás, pero este es un proceso muy lento que requiere administrar muchas cadenas largas en la memoria, lo que hace que mi programa sea bastante lento.

¿Alguna idea de cómo se puede acelerar esto para múltiples cadenas? Gracias.

Edición importante Una de las variables que me dan determina la cantidad de cadenas en las que debe estar la subcadena más larga, por lo que me pueden dar 10 cadenas y encontrar el LCS de todas ellas (K = 10), o LCS de 4 de ellos, pero no me dicen que 4, tengo que encontrar el mejor 4.

Aquí hay una versión de C # para encontrar la subcadena común más larga utilizando la programación dinámica de dos arreglos (puede consultar: http://codingworkout.blogspot.com/2014/07/longest-common-substring.html para obtener más detalles)

class LCSubstring { public int Length = 0; public List<Tuple<int, int>> indices = new List<Tuple<int, int>>(); } public string[] LongestCommonSubStrings(string A, string B) { int[][] DP_LCSuffix_Cache = new int[A.Length+1][]; for (int i = 0; i <= A.Length; i++) { DP_LCSuffix_Cache[i] = new int[B.Length + 1]; } LCSubstring lcsSubstring = new LCSubstring(); for (int i = 1; i <= A.Length; i++) { for (int j = 1; j <= B.Length; j++) { //LCSuffix(Xi, Yj) = 0 if X[i] != X[j] // = LCSuffix(Xi-1, Yj-1) + 1 if Xi = Yj if (A[i - 1] == B[j - 1]) { int lcSuffix = 1 + DP_LCSuffix_Cache[i - 1][j - 1]; DP_LCSuffix_Cache[i][j] = lcSuffix; if (lcSuffix > lcsSubstring.Length) { lcsSubstring.Length = lcSuffix; lcsSubstring.indices.Clear(); var t = new Tuple<int, int>(i, j); lcsSubstring.indices.Add(t); } else if(lcSuffix == lcsSubstring.Length) { //may be more than one longest common substring lcsSubstring.indices.Add(new Tuple<int, int>(i, j)); } } else { DP_LCSuffix_Cache[i][j] = 0; } } } if(lcsSubstring.Length > 0) { List<string> substrings = new List<string>(); foreach(Tuple<int, int> indices in lcsSubstring.indices) { string s = string.Empty; int i = indices.Item1 - lcsSubstring.Length; int j = indices.Item2 - lcsSubstring.Length; Assert.IsTrue(DP_LCSuffix_Cache[i][j] == 0); for(int l =0; l<lcsSubstring.Length;l++) { s += A[i]; Assert.IsTrue(A[i] == B[j]); i++; j++; } Assert.IsTrue(i == indices.Item1); Assert.IsTrue(j == indices.Item2); Assert.IsTrue(DP_LCSuffix_Cache[i][j] == lcsSubstring.Length); substrings.Add(s); } return substrings.ToArray(); } return new string[0]; }

Donde las pruebas unitarias son:

[TestMethod] public void LCSubstringTests() { string A = "ABABC", B = "BABCA"; string[] substrings = this.LongestCommonSubStrings(A, B); Assert.IsTrue(substrings.Length == 1); Assert.IsTrue(substrings[0] == "BABC"); A = "ABCXYZ"; B = "XYZABC"; substrings = this.LongestCommonSubStrings(A, B); Assert.IsTrue(substrings.Length == 2); Assert.IsTrue(substrings.Any(s => s == "ABC")); Assert.IsTrue(substrings.Any(s => s == "XYZ")); A = "ABC"; B = "UVWXYZ"; string substring = ""; for(int i =1;i<=10;i++) { A += i; B += i; substring += i; substrings = this.LongestCommonSubStrings(A, B); Assert.IsTrue(substrings.Length == 1); Assert.IsTrue(substrings[0] == substring); } }

Encuentra la mayor subcadena de todas las cadenas bajo consideración. De N cuerdas, tendrás N subcadenas. Elige el más grande de esos N.

Este es un problema de programación dinámica y puede resolverse en tiempo O (mn), donde m es la longitud de una cadena yn es otra.

Como cualquier otro problema resuelto usando la Programación Dinámica, dividiremos el problema en un subproblema. Digamos si dos cadenas son x1x2x3 .... xm y y1y2y3 ... yn

S (i, j) es la cadena común más larga para x1x2x3 ... xi y y1y2y3 .... yj, entonces

S (i, j) = max {longitud de la subcadena común más larga que termina en xi / yj, si (x [i] == y [j]), S (i-1, j-1), S (i, j -1), S (i-1, j)}

Aquí está el programa de trabajo en Java. Estoy seguro de que puedes convertirlo a C ++ .:

public class LongestCommonSubstring { public static void main(String[] args) { String str1 = "abcdefgijkl"; String str2 = "mnopabgijkw"; System.out.println(getLongestCommonSubstring(str1,str2)); } public static String getLongestCommonSubstring(String str1, String str2) { //Note this longest[][] is a standard auxialry memory space used in Dynamic //programming approach to save results of subproblems. //These results are then used to calculate the results for bigger problems int[][] longest = new int[str2.length() + 1][str1.length() + 1]; int min_index = 0, max_index = 0; //When one string is of zero length, then longest common substring length is 0 for(int idx = 0; idx < str1.length() + 1; idx++) { longest[0][idx] = 0; } for(int idx = 0; idx < str2.length() + 1; idx++) { longest[idx][0] = 0; } for(int i = 0; i < str2.length(); i++) { for(int j = 0; j < str1.length(); j++) { int tmp_min = j, tmp_max = j, tmp_offset = 0; if(str2.charAt(i) == str1.charAt(j)) { //Find length of longest common substring ending at i/j while(tmp_offset <= i && tmp_offset <= j && str2.charAt(i - tmp_offset) == str1.charAt(j - tmp_offset)) { tmp_min--; tmp_offset++; } } //tmp_min will at this moment contain either < i,j value or the index that does not match //So increment it to the index that matches. tmp_min++; //Length of longest common substring ending at i/j int length = tmp_max - tmp_min + 1; //Find the longest between S(i-1,j), S(i-1,j-1), S(i, j-1) int tmp_max_length = Math.max(longest[i][j], Math.max(longest[i+1][j], longest[i][j+1])); if(length > tmp_max_length) { min_index = tmp_min; max_index = tmp_max; longest[i+1][j+1] = length; } else { longest[i+1][j+1] = tmp_max_length; } } } return str1.substring(min_index, max_index >= str1.length() - 1 ? str1.length() - 1 : max_index + 1); } }

Hay una solución de programación dinámica muy elegante para esto.

Sea LCSuff[i][j] el sufijo común más largo entre X[1..m] e Y[1..n] . Aquí tenemos dos casos:

  • X[i] == Y[j] , eso significa que podemos extender el sufijo común más largo entre X[i-1] e Y[j-1] . Por LCSuff[i][j] = LCSuff[i-1][j-1] + 1 tanto, LCSuff[i][j] = LCSuff[i-1][j-1] + 1 en este caso.

  • X[i] != Y[j] , ya que los últimos caracteres son diferentes, X[1..i] e Y[1..j] no pueden tener un sufijo común. Por lo tanto, LCSuff[i][j] = 0 en este caso.

Ahora necesitamos verificar el máximo de estos sufijos comunes más largos.

Entonces, LCSubstr(X,Y) = max(LCSuff(i,j)) , donde 1<=i<=m 1<=j<=n

El algoritmo prácticamente se escribe a sí mismo ahora.

string LCSubstr(string x, string y){ int m = x.length(), n=y.length(); int LCSuff[m][n]; for(int j=0; j<=n; j++) LCSuff[0][j] = 0; for(int i=0; i<=m; i++) LCSuff[i][0] = 0; for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ if(x[i-1] == y[j-1]) LCSuff[i][j] = LCSuff[i-1][j-1] + 1; else LCSuff[i][j] = 0; } } string longest = ""; for(int i=1; i<=m; i++){ for(int j=1; j<=n; j++){ if(LCSuff[i][j] > longest.length()) longest = x.substr((i-LCSuff[i][j]+1) -1, LCSuff[i][j]); } } return longest; }

Probé varias soluciones diferentes para esto, pero todas parecían muy lentas, así que se me ocurrió lo siguiente, realmente no probé mucho, pero parece funcionar un poco más rápido para mí.

#include <iostream> std::string lcs( std::string a, std::string b ) { if( a.empty() || b.empty() ) return {} ; std::string current_lcs = ""; for(int i=0; i< a.length(); i++) { size_t fpos = b.find(a[i], 0); while(fpos != std::string::npos) { std::string tmp_lcs = ""; tmp_lcs += a[i]; for (int x = fpos+1; x < b.length(); x++) { tmp_lcs+=b[x]; size_t spos = a.find(tmp_lcs, 0); if (spos == std::string::npos) { break; } else { if (tmp_lcs.length() > current_lcs.length()) { current_lcs = tmp_lcs; } } } fpos = b.find(a[i], fpos+1); } } return current_lcs; } int main(int argc, char** argv) { std::cout << lcs(std::string(argv[1]), std::string(argv[2])) << std::endl; }