Algoritmo de encadenamiento de cadena

Question

Estoy buscando un algoritmo eficiente para hacer cadena de embaldosado. Básicamente, se le da una lista de cadenas, dice BCD, CDE, ABC, A, y la consiguiente baldosas cadena debe ser ABCDE, porque BCD se alinea con CDE cediendo BCDE, que es luego alineado con ABC obteniéndose el ABCDE final.

Actualmente, estoy usando un algoritmo ligeramente ingenuo, que funciona de la siguiente manera. A partir de un par aleatoria de cadenas, por ejemplo BCD y CDE, utilizo el siguiente (en Java):

public static String tile(String first, String second) { 
    for (int i = 0; i < first.length() || i < second.length(); i++) { 
    // "right" tile (e.g., "BCD" and "CDE") 
    String firstTile = first.substring(i); 
    // "left" tile (e.g., "CDE" and "BCD") 
    String secondTile = second.substring(i); 
    if (second.contains(firstTile)) { 
     return first.substring(0, i) + second; 
    } else if (first.contains(secondTile)) { 
     return second.substring(0, i) + first; 
    } 
    } 
    return EMPTY; 
} 

System.out.println(tile("CDE", "ABCDEF")); // ABCDEF 
System.out.println(tile("BCD", "CDE")); // BCDE 
System.out.println(tile("CDE", "ABC")); // ABCDE 
System.out.println(tile("ABC", tile("BCX", "XYZ"))); // ABCXYZ 

Aunque esto funciona, no es muy eficiente, ya que itera sobre los mismos personajes una y otra vez.

Entonces, ¿alguien sabe mejor (más eficiente) algoritmo para hacer esto? Este problema es similar a un problema de alineación de secuencia de ADN, por lo que cualquier consejo de alguien en este campo (y otros, por supuesto) son bienvenidos. También tenga en cuenta que no estoy buscando una alineación , sino un mosaico, porque necesito una superposición completa de una de las cadenas sobre la otra.

Actualmente estoy buscando una adaptación del Rabin-Karp algorithm, para mejorar la complejidad asintótica del algoritmo, pero me gustaría escuchar algunos consejos antes de profundizar más en este asunto.

Gracias de antemano.

---

Para situaciones donde hay ambigüedad - por ejemplo, {ABC, CBA} que podría resultar en ABCBA o CBABC -, pueden ser devueltos cualquier suelo de baldosas. Sin embargo, esta situación rara vez ocurre, porque estoy embaldosando palabras, p. {This is, is me} => {This is me}, que se manipulan para que el algoritmo mencionado funcione.

Pregunta similar: Efficient Algorithm for String Concatenation with Overlap

Answer 1

Lo primero que debe hacerse es si usted desea encontrar el laboreo de {CDB, CDA}? No hay labranza única.

Answer 2

Creo que esto debería funcionar para el mosaico de dos cadenas, y ser más eficiente que su implementación actual que utiliza subcadena y contiene. Conceptualmente, recorro los caracteres en la cadena 'izquierda' y los comparo con un carácter en la cadena 'derecha'. Si los dos personajes coinciden, me muevo al siguiente personaje en la cadena derecha. Dependiendo de la cadena a la que se llegue por primera vez al final, y si coinciden o no los últimos caracteres comparados, se identifica uno de los posibles casos de mosaico.

No he pensado en nada para mejorar la complejidad del tiempo de mosaico de más de dos cadenas. Como una pequeña nota para múltiples cadenas, este algoritmo a continuación se extiende fácilmente para verificar el mosaico de una única cadena 'izquierda' con múltiples cadenas 'derechas' a la vez, lo que podría evitar un bucle extra sobre las cuerdas un poco si estás tratando de averiguar si hacer ("ABC", "BCX", "XYZ") o ("ABC", "XYZ", BCX ") con solo probar todas las posibilidades. Un poco.

string Tile(string a, string b) 
{ 
    // Try both orderings of a and b, 
    // since TileLeftToRight is not commutative. 

    string ab = TileLeftToRight(a, b); 

    if (ab != "") 
     return ab; 

    return TileLeftToRight(b, a); 

    // Alternatively you could return whichever 
    // of the two results is longest, for cases 
    // like ("ABC" "BCABC"). 
} 

string TileLeftToRight(string left, string right) 
{ 
    int i = 0; 
    int j = 0; 

    while (true) 
    { 
     if (left[i] != right[j]) 
     { 
      i++; 

      if (i >= left.Length) 
       return ""; 
     } 
     else 
     { 
      i++; 
      j++; 

      if (i >= left.Length) 
       return left + right.Substring(j); 

      if (j >= right.Length) 
       return left; 
     } 
    } 
} 

Answer 3

Orden de las cuerdas por el primer carácter, entonces la longitud (menor a mayor), y luego aplicar la adaptación a KMP encuentran en this question sobre la concatenación de cadenas superpuestas.

Answer 4

Problema interesante. Necesitas algún tipo de retroceso. Por ejemplo, si usted tiene:

ABC, BCD, DBC 

combinación con DBC básico tiene como resultado:

ABC, DBCD 

Lo que no tiene solución. Pero la combinación de ABC con resultados BCD en:

ABCD, DBC

que se pueden combinar con:

ABCDBC. 

Answer 5

Si el código de fuente abierta es aceptable, entonces usted debe comprobar la genoma puntos de referencia en Stanford STAMP suite de referencia: hace más o menos exactamente lo que estás buscando. Comenzando con un grupo de cadenas ("genes"), busca la cadena más corta que incorpore todos los genes. Entonces, por ejemplo, si tiene ATGC y GCAA, encontrará ATGCAA. No hay nada sobre el algoritmo que lo limite a un alfabeto de 4 caracteres, por lo que debería poder ayudarte.