Subcadena común más larga

En informática , la subcadena común más larga de dos o más cadenas es la cadena más larga que es subcadena de todas ellas. Puede haber más de una subcadena común más larga. Entre sus aplicaciones se incluyen la deduplicación de datos y la detección de plagio .

A diferencia del problema de la subsecuencia común más larga , que encuentra inserciones o eliminaciones dentro del texto común, el problema de la subcadena común más larga busca una subcadena contigua compartida por ambos textos.

La imagen muestra dos cadenas de caracteres donde el problema tiene múltiples soluciones. Aunque las ocurrencias de las subcadenas siempre se superponen, es imposible obtener una subcadena común más larga "uniéndolas".

Las cadenas "ABABC", "BABCA" y "ABCBA" tienen solo una subcadena común más larga, a saber, "ABC" de longitud 3. Otras subcadenas comunes son "A", "AB", "B", "BA", "BC" y "C".

 ABABC ||| BABCA ||| ABCBA

Dadas dos cadenas,${\displaystyle S}$de longitud${\displaystyle m}$y${\displaystyle T}$de longitud${\displaystyle n}$, encontrar la cadena más larga que sea una subcadena de ambas${\displaystyle S}$y${\displaystyle T}$.

Una generalización es el problema de la subcadena k - común . Dado el conjunto de cadenas${\displaystyle S=\{S_{1},\ldots ,S_{K}\}}$, dónde${\displaystyle |S_{i}|=n_{i}}$y${\textstyle \sum n_{i}=N}$. Encuentra para cada${\displaystyle 2\leq k\leq K}$, la cadena más larga que aparece como subcadena de al menos${\displaystyle k}$instrumentos de cuerda.

Se pueden encontrar las longitudes y las posiciones iniciales de las subcadenas comunes más largas de${\displaystyle S}$y${\displaystyle T}$en${\displaystyle \Theta }$${\displaystyle (n+m)}$tiempo con la ayuda de un árbol de sufijos generalizado . Se puede lograr un algoritmo más rápido en el modelo de computación de memoria RAM de palabras si el tamaño${\displaystyle \sigma }$del alfabeto de entrada está en${\displaystyle 2^{o\left({\sqrt {\log(n+m)}}\right)}}$. En particular, este algoritmo se ejecuta en${\textstyle O\left((n+m)\log \sigma /{\sqrt {\log(n+m)}}\right)}$tiempo usando${\displaystyle O\left((n+m)\log \sigma /\log(n+m)\right)}$espacio. ^{[ 1 ]} Resolver el problema mediante programación dinámica cuesta${\displaystyle \Theta (nm)}$Las soluciones al problema generalizado toman${\displaystyle \Theta (n_{1}+\cdots +n_{K})}$espacio y${\displaystyle \Theta (n_{1}\cdots n_{K})}$tiempo con programación dinámica y tomar${\displaystyle \Theta (n_{1}+\cdots +n_{K})}$tiempo con un árbol de sufijos generalizado .

árbol de sufijos

Las subcadenas comunes más largas de un conjunto de cadenas se pueden encontrar construyendo un árbol de sufijos generalizado para las cadenas y luego encontrando los nodos internos más profundos que tienen nodos hoja de todas las cadenas en el subárbol inferior. La figura de la derecha muestra 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.

Construir el árbol de sufijos lleva${\displaystyle \Theta (N)}$tiempo (si el tamaño del alfabeto es constante). Si el árbol se recorre de abajo hacia arriba con un vector de bits que indica qué cadenas se ven debajo de cada nodo, el problema de la subcadena común k se puede resolver en${\displaystyle \Theta (NK)}$tiempo. Si el árbol de sufijos está preparado para la recuperación del ancestro común más bajo en tiempo constante , se puede resolver en${\displaystyle \Theta (N)}$tiempo. ^{[ 2 ]}

función SubcadenaComúnMásLarga(S[1..r], T[1..n]) L := arreglo (1..r, 1..n) z := 0 # longitud de la subcadena común más larga encontrada hasta ahora 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 regresar​

• Subcadena palíndroma más larga
• n -grama , todas las subcadenas posibles de longitud n que están contenidas en una cadena.

• Diccionario de algoritmos y estructuras de datos: subcadena común más larga
• Implementación en Perl/XS del algoritmo de programación dinámica
• Implementación en Perl/XS del algoritmo de árbol de sufijos
• Implementaciones de programación dinámica en varios lenguajes en Wikilibros
• Implementación funcional en AS3 del algoritmo de programación dinámica
• Implementación en C basada en árbol de sufijos para la subcadena común más larga entre dos cadenas.