java - macarena - Atascado encontrando el camino más profundo en el cruce de árboles en general tratando de encontrar la subcadena común más grande

fosa comun de la macarena

Question

Estoy tratando de resolver el problema de la subcadena común más grande entre 2 cadenas. Reduciré mi problema a lo siguiente: creé un árbol de sufijo general y, según mi comprensión, la subcadena común más grande es la ruta más profunda que consta de nodos que pertenecen a ambas cadenas.

Mi entrada de prueba es:

String1 = xabc
String2 = abc

Parece que el árbol que construyo es correcto, pero mi problema es el siguiente (paso primero la raíz del árbol):

private void getCommonSubstring(SuffixNode node) {
if(node == null)
return;
if(node.from == ComesFrom.Both){
current.add(node);
}
else{
if(max == null || current.size() > max.size()){
max = current;
}
current = new ArrayList<SuffixNode>();
}
for(SuffixNode n:node.children){
getCommonSubstring(n);
}
} 

Lo que pretendía hacer es encontrar el camino más profundo con nodos que pertenecen a ambas cadenas, atravesaría el árbol (preordenar) y agregaría nodos que pertenecen a ambas cadenas en una lista ( current ). Una vez que estoy en un nodo que no forma parte de ambos, actualizo la lista max si la current es más grande.

Pero el código es erróneo. Y estoy confundido sobre cómo implementar esto, ya que no he escrito código para árboles generales (no binarios) en años.

¿Podrías ayudarme a resolver esto?

Actualizar:
Modificado según @templatetypedef. No podría hacer que esto funcione tampoco.

private void getCommonSubstring(SuffixNode node, List<SuffixNode> nodes) {
if(node == null)
return;
if(node.from == ComesFrom.Both){
nodes.add(node);
}
else{
if(max == null || current.size() > max.size()){
max = nodes;
}
nodes = new ArrayList<SuffixNode>();
}
for(SuffixNode n:node.children){
List<SuffixNode> tmp = new ArrayList<SuffixNode>(nodes);
getCommonSubstring(n, tmp);
}
}
public class SuffixNode {
Character character;
Collection<SuffixNode> children;
ComesFrom from;
Character endMarker;
} 

Answer 1

¿TIENES que ir por la ruta de un árbol de sufijos? Si no, ¿por qué no podrías:

public String findCommonSubString(string str1, string str2) {
string mainStr;
string otherStr;
string commonStr = "";
string foundCommonStr = "";
boolean strGrowing = false;
If (str1.length() > str2.length()) {
mainStr = str1;
otherStr = str2;
} else {
mainStr = str2;
otherStr = str1;
}
int strCount = 0;
for(int x = 0; x < mainStr.length();x++) {
strCount = 1;
strGrowing = true;
while(strGrowing) {
if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
//Found a match now add a character to it.
strCount++;
foundCommonStr = mainStr.substring(x, strCount);
if (foundCommonStr.length() > commonStr.length()) {
commonStr = foundCommonStr;
}
} else {
strGrowing = false;
}
}
}
return commonStr;
}

No he corrido esto ... pero lo haré. Básicamente, esto comenzará con la más pequeña de las dos cadenas e intentará encontrar una cadena común entre las dos cadenas usando IndexOf y subserie. luego, si lo hace, se volverá a verificar, pero esta vez, compruebe añadiendo un carácter más de la cadena más pequeña al cheque. Solo almacenará la cadena en la variable commonStr si la cadena encontrada (foundCommonStr) es más grande que commonStr. Si no encuentra una coincidencia, entonces ya ha almacenado el commonStr más grande para ser devuelto.

Creo que la idea es sólida, pero no la he ejecutado en el compilador.

Answer 2

Aunque no es una respuesta, así es como lo resolvería usando colecciones estándar con búsqueda O (n log n).

static String findLongestCommonSubstring(String s1, String s2) {
if (s1.length() > s2.length()) return findLongestCommonSubstring(s2, s1);
NavigableSet<String> substrings = new TreeSet<>();
for (int i = 0; i < s1.length(); i++)
substrings.add(s1.substring(i));
String longest = "";
for (int i = 0; i < s2.length(); i++) {
String sub2 = s2.substring(i);
String floor = match(substrings.floor(sub2), sub2);
String ceiling = match(substrings.ceiling(sub2), sub2);
if (floor.length() > longest.length())
longest = floor;
if (ceiling.length() > longest.length())
longest = ceiling;
}
return longest;
}
private static String match(String s1, String s2) {
if (s1 == null || s2 == null) return "";
for (int i = 0; i < s1.length() && i < s2.length(); i++)
if (s1.charAt(i) != s2.charAt(i))
return s1.substring(0, i);
return s1.substring(0, Math.min(s1.length(), s2.length()));
}
public static void main(String... args) {
System.out.println(findLongestCommonSubstring("sdlkjfsdkljfkljsdlfkjaeakjf", "kjashdkasjdlkjasdlfkjaesdlk"));
}

huellas dactilares

sdlfkjae

Answer 3

Un problema que veo aquí es que la profundidad de un nodo en el árbol de sufijo no es la misma que la longitud de la cadena a lo largo de esa ruta. Cada borde en un árbol de sufijo se anota con un rango de caracteres, por lo que una cadena codificada por una serie de nodos de profundidad cinco podría tener una longitud más corta que una cadena codificada en profundidad dos. Probablemente necesite ajustar su algoritmo para manejar esto mediante el seguimiento de la longitud efectiva de la cadena que ha creado hasta el momento, en lugar de la cantidad de nodos en la ruta que ha trazado hasta este punto.

Un segundo problema que acabo de notar es que parece que solo tiene una variable current que se está compartiendo en todas las diferentes ramas de la recursión. Esto probablemente está arruinando tu estado a través de llamadas recursivas. Por ejemplo, supongamos que se encuentra en un nodo y tiene una ruta de longitud tres, y que hay dos hijos, el primero de los cuales solo termina en un sufijo de la primera cadena, y el segundo termina en un sufijo de ambas cadenas. En ese caso, si realiza la llamada recursiva en la primera cadena, terminará ejecutando la línea

current = new ArrayList<SuffixNode>(); 

en la llamada recursiva. Esto borrará todo su historial, de modo que cuando regrese de esta llamada al nodo original y descienda al segundo nodo secundario, actuará como si no hubiera una lista de nodos acumulados hasta el momento, en lugar de continuar desde los tres nodos que encontraste hasta ahora.

Para solucionar esto, sugeriría convertir un parámetro current a la función y luego crear una nueva lista de ArrayList cuando sea necesario, en lugar de aniquilar la lista de ArrayList existente. Parte de la otra lógica podría tener que cambiar también para dar cuenta de esto.

Dado esto, sugeriría escribir la función en un pseudocódigo como este (ya que no conozco los detalles de las implementaciones de su árbol de sufijos):

• Si el nodo actual es nulo, devuelve 0.
• Si el nodo actual no proviene de ambas cadenas, devuelve 0.
• De otra manera:
  • Establecer maxLen = 0.
  • Para cada nodo hijo:
    • Calcule la longitud de la subcadena común más larga enraizada en ese nodo.
    • Agregue a esa longitud la cantidad de caracteres a lo largo del borde para ese niño.
    • Actualice maxLen si esto excede el valor anterior.
  • Devuelve maxLen.

¡Espero que esto ayude!

Answer 4

public String findCommonSubString(string str1, string str2) {
string mainStr;
string otherStr;
string commonStr = "";
string foundCommonStr = "";
boolean strGrowing = false;
If (str1.length() > str2.length()) {
mainStr = str1;
otherStr = str2;
} else {
mainStr = str2;
otherStr = str1;
}
int strCount = 0;
for(int x = 0; x < mainStr.length();x++) {
strCount = 1;
strGrowing = true;
while(strGrowing) {
if (otherStr.IndexOf(mainStr.substring(x, strCount) >= 0) {
//Found a match now add a character to it.
strCount++;
foundCommonStr = mainStr.substring(x, strCount);
if (foundCommonStr.length() > commonStr.length()) {
commonStr = foundCommonStr;
}
} else {
strGrowing = false;
}
}
}
return commonStr;
}