En ciencias de la computación , el problema de subcadena común más largo es encontrar la cadena más larga que es una subcadena de dos o más cadenas. El problema puede tener múltiples soluciones. Las aplicaciones incluyen la deduplicación de datos y la detección de plagio .
Ejemplo
La subcadena común más larga de las cadenas "ABABC", "BABCA" y "ABCBA" es la cadena "ABC" de longitud 3. Otras subcadenas comunes son "A", "AB", "B", "BA", "BC" y C".
ABABC ||| BABCA ||| ABCBA
Definición del problema
Dadas dos cuerdas, de longitud y de longitud , encuentre la cadena más larga que sea la subcadena de ambos y .
Una generalización es el problema de la subcadena k-común . Dado el conjunto de cuerdas, dónde y . Encuentra para cada, las cadenas más largas que ocurren como subcadenas de al menos instrumentos de cuerda.
Algoritmos
Uno puede encontrar las longitudes y posiciones iniciales de las subcadenas comunes más largas de y en tiempo con la ayuda de un árbol de sufijos generalizados . Encontrarlos por costos de programación dinámicos. Las soluciones al problema generalizado toman espacio y · ... ·tiempo con programación dinámica y tomatiempo con árbol de sufijo generalizado .
Árbol de sufijo
Las subcadenas comunes más largas de un conjunto de cadenas se pueden encontrar construyendo un árbol de sufijos generalizados para las cadenas y luego encontrando los nodos internos más profundos que tienen nodos hoja de todas las cadenas en el subárbol debajo de él. La figura de la derecha es el árbol de sufijos para las cadenas "ABAB", "BABA" y "ABBA", rellenas con terminadores de cadena únicos, para convertirse en "ABAB $ 0", "BABA $ 1" y "ABBA $ 2". Los nodos que representan "A", "B", "AB" y "BA" tienen hojas descendientes de todas las cadenas, numeradas 0, 1 y 2.
La construcción del árbol de sufijos requiere tiempo (si el tamaño del alfabeto es constante). Si el árbol se atraviesa de abajo hacia arriba con un vector de bits que indica qué cadenas se ven debajo de cada nodo, el problema de k subcadenas comunes se puede resolver enhora. Si el árbol de sufijos está preparado para la recuperación del ancestro común más bajo en tiempo constante , se puede resolver enhora. [1]
Programación dinámica
El siguiente pseudocódigo encuentra el conjunto de subcadenas comunes más largas entre dos cadenas con programación dinámica:
función LCSubstr (S [1..r], T [1..n]) L: = matriz (1..r, 1..n) z: = 0 ret: = {} para i: = 1..r para j: = 1..n si S [i] = T [j] si i = 1 o j = 1 L [i, j]: = 1 demás L [i, j]: = L [i - 1, j - 1] + 1 si L [i, j]> z z: = L [i, j] ret: = {S [i - z + 1..i]} de lo contrario, si L [i, j] = z ret: = ret ∪ {S [i - z + 1..i]} demás L [i, j]: = 0 volver ret
Este algoritmo se ejecuta en hora. La matriz de L
las tiendas de la subsecuencia común más larga de los prefijos S[1..i]
y T[1..j]
que terminan en la posición S[i]
, T[j]
, resp. La variable z
se usa para contener la longitud de la subcadena común más larga encontrada hasta ahora. El juego ret
se usa para sostener el juego de cuerdas que son de longitud z
. El conjunto ret
se puede guardar de manera eficiente simplemente almacenando el índice i
, que es el último carácter de la subcadena común más larga (de tamaño z) en lugar de S[i-z+1..i]
. Por lo tanto todas las subcadenas comunes serían más largas, para cada i en ret
, S[(ret[i]-z)..(ret[i])]
.
Los siguientes trucos se pueden utilizar para reducir el uso de memoria de una implementación:
- Conserve solo la última fila y la actual de la tabla DP para ahorrar memoria ( en vez de )
- Almacene solo valores distintos de cero en las filas. Esto se puede hacer usando tablas hash en lugar de matrices. Esto es útil para alfabetos grandes.
Ver también
- Subcadena palindrómica más larga
- n -grama , todas las posibles subcadenas de longitud n que están contenidas en una cadena
Referencias
- ^ Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . Estados Unidos: Cambridge University Press. ISBN 0-521-58519-8.
enlaces externos
- Diccionario de algoritmos y estructuras de datos: subcadena común más larga
- Implementación Perl / XS del algoritmo de programación dinámica
- Implementación de Perl / XS del algoritmo de árbol de sufijos
- Implementaciones de programación dinámica en varios lenguajes en wikilibros
- Implementación AS3 funcional del algoritmo de programación dinámica.
- Implementación de C basada en árbol de sufijo de la subcadena común más larga para dos cadenas