Buscador de Subcadenas Comunes

¿Qué es el Buscador de Subcadenas Comunes y cómo funciona el Algoritmo LCS?

El Buscador de Subcadenas Comunes es una herramienta algorítmica de computación sobre cadenas (*string processing*) y procesamiento de lenguaje natural diseñada para localizar, extraer y clasificar todas las secuencias contiguas de caracteres o frases compartidas de forma idéntica entre dos textos, identificando automáticamente la Subcadena Común Más Larga (Longest Common Substring - LCS).

En informática teórica y bioinformática, el problema de la subcadena común más larga es una de las tareas clásicas de coincidencia de patrones con aplicaciones cruciales en: detección de código duplicado o clones de software (*refactoring*), cotejo de secuencias genéticas (alineamiento local tipo Smith-Waterman / BLAST), detección forense de plagio literal, auditoría de cláusulas en contratos jurídicos y análisis de diffs textuales.

Nuestra herramienta implementa un motor de Programación Dinámica optimizada en tiempo $\mathcal{O}(m \cdot n)$ y espacio lineal $\mathcal{O}(n)$, permitiendo filtrar por longitud mínima de coincidencia ($k \ge 3, 4, 5, 8, 10$ caracteres) y alternar sensibilidad a mayúsculas. Incluye un visor sincronizado interactivo que resalta en tiempo real todos los fragmentos coincidentes en Documento A y Documento B, calculando el porcentaje exacto de cobertura y generando una tabla ordenada por longitud y frecuencia. Puedes complementar tu análisis con el Detector de Plagio de Texto Online o la Calculadora de Distancia Levenshtein.

Diferencia Fundamental: Subcadena Común (LCS) vs Subsecuencia Común (LCSeq)

Es crucial distinguir entre dos conceptos computacionales a menudo confundidos en la literatura:

• Subcadena Común (Substring - Contigua): Los caracteres coincidentes deben aparecer de forma estrictamente consecutiva sin interrupciones ni caracteres intercalados. Ejemplo: en «ABABC» y «BABCA», la subcadena común más larga es «BABC» (4 caracteres consecutivos).
• Subsecuencia Común (Subsequence - No necesariamente contigua): Los caracteres deben aparecer en el mismo orden relativo, pero pueden existir otros elementos intercalados entre ellos. Ejemplo: en «ABAZDC» y «BACBAD», una subsecuencia común es «ABAD».

Algoritmo de Programación Dinámica para la Subcadena Más Larga

Dadas dos cadenas $S_1$ de longitud $m$ y $S_2$ de longitud $n$, definimos una matriz $L[i, j]$ que almacena la longitud del sufijo común más largo de los prefijos $S_1[1..i]$ y $S_2[1..j]$:

El algoritmo recorre la matriz identificando el valor máximo. Al resetear la celda a $0$ cuando $S_1[i] \neq S_2[j]$, se garantiza la estricta contigüidad de la coincidencia. La subcadena óptima se recupera tomando el segmento $S_1[i_{\max} - \text{LCS} + 1 \,..\, i_{\max}]$.

Tabla Comparativa: Algoritmos de Búsqueda de Subcadenas

Preguntas Frecuentes (FAQ)