¿Cuál es la mejor estructura de datos y el algoritmo para comparar una lista de cadenas?

Question

Quiero encontrar la secuencia más larga posible de palabras que coinciden con las reglas siguientes:

• Cada palabra se puede utilizar como máximo una vez
• Todas las palabras son cadenas
• sa y sb dos cadenas se pueden concatenar si las dos últimas letras de sa coincide con los dos primeros caracteres de sb.

En el caso de concatenación, se realiza mediante la superposición de esos caracteres. Por ejemplo:

• sa = "torino"
• sb = "Novara"
• sa concat sb = "torinovara"

Por ejemplo, tengo el siguiente archivo de entrada, "entrada.txt":

Novara

Torino

Vercelli

ravenna

Napoli

Liverno

messania

Novi Ligure

roma

Y, la salida del archivo anterior de acuerdo con las reglas anteriores debe ser:

Torino

Novara

ravenna

Napoli

Livorno

Novi Ligure

desde la concatenación más larga posible es:

torinovaravennapolivornovilligure

Puede alguien por favor me ayude con esto? ¿Cuál sería la mejor estructura de datos para esto?

Answer 1

Esto puede ser presentado como un problema gráfico dirigido - los nodos son palabras, y están conectados por un borde si se superponen (y se elige el solapamiento más pequeño para obtener la longitud más larga), y después encontrar la más alta no peso camino -intersecting.

(Bueno, en realidad, desea ampliar el gráfico un poco de manejar comenzando y terminando en una palabra. Adjoin un "nodo de partida" con un borde a cada palabra de longitud peso palabra / 2. Entre las palabras, -overlap + longitud de inicio + longitud final / 2, y entre cada palabra y un "nodo de finalización" "longitud de palabra / 2". Podría ser más fácil doblarlo.)

https://cstheory.stackexchange.com/questions/3684 / max-no superpuestas-path-en-ponderado gráfico

Answer 2

Me gustaría empezar realmente simple. Hacer 2 vectores de cadenas, uno ordenados normalmente, uno ordenado por las 2 últimas letras. Crear un índice (vector de enteros) para el segundo vector que señala el mismo de la posición en la primera.

Para encontrar la más larga .. saca primero la huérfanos. palabras que no coinciden en cada extremo para nada. A continuación, se quiere construir un vecino unirse árbol, aquí es donde se determina qué palabras posiblemente pueden llegar a unos de otros. Si usted tiene 2 o más árboles que debe tratar el árbol más grande primero.

Ahora, con un árbol de su trabajo es encontrar extremos que son raros, y se unen a otros fines, y repetir. Esto debe conseguir que una buena solución bastante, si se utiliza todas las palabras que su oro, omita los otros árboles. Si no lo hace, entonces su en toda una serie de algoritmos para hacer de este eficiente.

Algunos elementos a tener en cuenta: Si usted tiene más de 3 extremos únicos que están garantizados para dejar 1+ palabras. Esto puede ser usado para podar sus intentos abajo mientras que la caza de una respuesta. recalcular extremos únicas a menudo. Los números impares de un fin dado a asegurar que uno debe dejarse caer (se obtiene 2 regalos de promoción en los extremos). palabras que se segregan de partidos puede ser, siempre se puede tirar a la de la última, y ??arruinar definitivamente las cuentas de otra manera. Usted puede ser capaz de crear pequeños anillos auto coincidentes, se puede tratar a estos como las palabras que coinciden con uno mismo, siempre y cuando no les huérfano cuando se crea. Esto puede hacer que el rendimiento fantástico, pero no hay garantías sobre una solución perfecta.

El espacio de búsqueda es el orden (N!) Una lista de millones de elementos puede ser difícil de demostrar una respuesta exacta. Por supuesto que podría estar pasando por alto algo.