Cómo acelerar el cálculo de la longitud de la subcadena más larga común?

Question

Tengo dos muy grandes cadenas y yo estoy tratando de averiguar su común más larga subcadena .

Una forma es utilizar árboles sufijo (se supone que tienen una muy buena complejidad, a través de una aplicación compleja), y la otra es el método dinámica de programación (ambos son mencionados en la página de Wikipedia vinculado anteriormente).

Uso de la programación dinámica

El problema es que el método de programación dinámica tiene un enorme tiempo de ejecución (complejidad es O(n*m), donde n y m son longitudes de las dos cadenas).

Lo que yo quiero saber (antes de saltar a aplicar sufijo árboles): ¿Es posible acelerar el algoritmo si sólo quiero saber la longitud de la subcadena común (y no el común subcadena en sí)

Answer 1

¿Será más rápido en la práctica? Si. Va a ser más rápido con respecto a Big-Oh? No. La solución de programación dinámica es siempre O (n * m).

El problema que podría encontrarse con el sufijo árboles es que el comercio de exploración tiempo lineal del árbol de sufijos para una pena enorme en el espacio. sufijo árboles son generalmente mucho más grande que la mesa que había necesidad de aplicar para una versión de programación dinámica del algoritmo. Dependiendo de la longitud de sus cadenas, es muy posible que la programación dinámica será más rápido.

Buena suerte:)

Answer 2

Estos hará que se ejecute más rápido, aunque todavía será O(nm).

Una optimización está en el espacio (que se podría ahorrar un poco de tiempo de la asignación) es de notar que LCSuff solo depende de la fila anterior - por lo tanto, si sólo se preocupan por la longitud, puede optimizar el espacio O(nm) a O(min(n,m)) <. / p>

La idea es mantener sólo dos filas -. La fila actual que está procesando, y la fila anterior que se acaba de procesar, y tirar el resto

Answer 3

Aquí hay un algoritmo simple que puede acabados en O ((m + n) * log (m + n)), y mucho más fácil de implementar en comparación con algoritmo de árbol de sufijos, que es O (m + n) tiempo de ejecución.

deje que comience con la longitud min común (minG) = 0, y la longitud común max (MaxL) = min (m + n) 1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL.

2. let L = (minL + maxL)/2

3. hash every substring of length L in S, with key = hash, val = startIndex.

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1.

El problema restante es cómo en Hash todo subcadena de longitud L en el tiempo O (n). Puede utilizar una fórmula polinómica de la siguiente manera:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p.

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];

Answer 4

de Myer algoritmo de vector de bits puede ayudar. Funciona mediante el uso de la manipulación de bits y es un enfoque mucho más rápido.