Mayor subcadena común
La subcadena común más larga es una subcadena de dos o más cadenas que tiene la longitud máxima.
Formalmente, la subcadena común más grande de cadenas es la cadena que satisface la condición , la operación significa que la cadena es una subcadena (posiblemente impropia) de la cadena .
La solución al problema de encontrar la subcadena común máxima para dos cadenas y , cuyas longitudes y respectivamente, es llenar la tabla con el tamaño de acuerdo con la siguiente regla, suponiendo que los caracteres de la cadena están numerados a partir de uno.
![\left\{{\begin{matriz}{rclr}A_{{0j}}&=&0,&j=0\ldots n,\\A_{{i0}}&=&0,&i=0\ldots m,\ \A_{{ij}}&=&0,&s_{1}[i]\neq s_{2}[j],i\neq 0,j\neq 0,\\A_{{ij}}&=&A_{ {i-1j-1}}+1,&s_{1}[i]=s_{2}[j],i\neq 0,j\neq 0.\end{matriz}}\right.](https://wikimedia.org/api/rest_v1/media/math/render/svg/05bca60338f467057593742d7931efc78ad47b72)
El número máximo en la tabla es la longitud de la subcadena común más larga, la subcadena misma:
y .
![s_{1}[u-A_{{uv}}+1]\ldots s_{1}[u]](https://wikimedia.org/api/rest_v1/media/math/render/svg/4968d6067c2747a45bdb66841720529f57bb7661)
![s_{2}[v-A_{{uv}}+1]\ldots s_{2}[v]](https://wikimedia.org/api/rest_v1/media/math/render/svg/3536560aa0e1a50b8a37d9823c0e41d037406272)
La tabla se completa con valores para las filas SUBSEQUENCE y SUBEUENCS :
SUBSECUENCIA 000000000000 S 0 1 00 1 0000000 U 00 2 0000 1 0000 B 000 3 00000000 E 00000 1 00 1 00 1 U 00 1 0000 1 0000 E 00000 1 00 2 00 1 N 0000000 3 0000000000 4 0 S 0 1 0000000 1 0000000 _ _Obtenga la subcadena UENC común más grande .
La complejidad de dicho algoritmo es O (mn) .
Véase también
- árbol de sufijos
- Algoritmos en cadenas
- Mayor subsecuencia común
Notas
| Instrumentos de cuerda | |
|---|---|
| Medidas de similitud de cadenas | |
| Búsqueda de subcadena | |
| palíndromos | |
| Alineación de secuencia | |
| Estructuras de sufijos | |
| Otro | |