En la teoría del lenguaje formal y la informática , una subcadena es una secuencia contigua de caracteres dentro de una cadena . Por ejemplo, " lo mejor de " es una subcadena de " Fue el mejor de los tiempos ". Esto no debe confundirse con subsecuencia , que es una generalización de subcadena. Por ejemplo, " Itwastimes " es una subsecuencia de " It was the best of times ", pero no una subcadena.
Los prefijos y sufijos son casos especiales de subcadenas. Un prefijo de una cadena es una subcadena de que ocurre al comienzo de ; del mismo modo, un sufijo de una cadena es una subcadena que se produce al final de .
La lista de todas las subcadenas de la cadena " apple " sería " apple ", " appl ", " pple ", " app ", " ppl ", " ple ", " ap ", " pp ", " pl ", " le "," a "," p "," l "," e "," "(observe la cadena vacía al final).
Subcadena
Una cuerda es una subcadena (o factor) [1] de una cadena si existen dos cadenas y tal que . En particular, la cadena vacía es una subcadena de cada cadena.
Ejemplo: la cadena ana
es igual a las subcadenas (y subsecuencias) de banana
en dos compensaciones diferentes:
plátano ||||| ana || ||| ana
La primera aparición se obtiene con b
y na
, mientras que la segunda aparición se obtiene con ban
y siendo la cadena vacía.
Una subcadena de una cadena es un prefijo de un sufijo de la cadena y, de manera equivalente, un sufijo de un prefijo; por ejemplo, nan
es un prefijo de nana
, que a su vez es un sufijo de banana
. Si es una subcadena de , también es una subsecuencia , que es un concepto más general. Las ocurrencias de un patrón dado en una cadena dada se pueden encontrar con un algoritmo de búsqueda de cadenas . Encontrar la cadena más larga que sea igual a una subcadena de dos o más cadenas se conoce como el problema de la subcadena común más larga . En la literatura matemática, las subcadenas también se denominan subpalabras (en América) o factores (en Europa). [ cita requerida ]
Prefijo
Una cuerda es un prefijo [1] de una cadena si existe una cadena tal que . Un prefijo adecuado de una cadena no es igual a la cadena en sí; [2] algunas fuentes [3] además restringen un prefijo adecuado para que no esté vacío. Un prefijo puede verse como un caso especial de una subcadena.
Ejemplo: la cadena ban
es igual a un prefijo (y subcadena y subsecuencia) de la cadena banana
:
plátano|||prohibición
El símbolo de subconjunto cuadrado se usa a veces para indicar un prefijo, de modo que denota que es un prefijo de . Esto define una relación binaria en cadenas, llamada relación de prefijo , que es un tipo particular de orden de prefijo .
Sufijo
Una cuerda es un sufijo [1] de una cadena si existe una cadena tal que . Un sufijo adecuado de una cadena no es igual a la propia cadena. Una interpretación más restringida es que tampoco está vacía [1] . Un sufijo puede verse como un caso especial de una subcadena.
Ejemplo: la cadena nana
es igual a un sufijo (y subcadena y subsecuencia) de la cadena banana
:
plátano |||| nana
Un árbol de sufijos para una cadena es una estructura de datos trie que representa todos sus sufijos. Los árboles de sufijos tienen un gran número de aplicaciones en algoritmos de cadenas . La matriz de sufijos es una versión simplificada de esta estructura de datos que enumera las posiciones iniciales de los sufijos en orden alfabético; tiene muchas de las mismas aplicaciones.
Frontera
Un borde es un sufijo y un prefijo de la misma cadena, por ejemplo, "bab" es un borde de "babab" (y también de "babooneatingakebab").
Supercuerda
Una supercuerda de un conjunto finito de cadenas es una sola cadena que contiene cada cadena en como una subcadena. Por ejemplo, es una supercuerda de , y es uno más corto. Generalmente, uno está interesado en encontrar supercuerdas cuya longitud sea lo más pequeña posible; [ aclaración necesaria ] una concatenación de todas las cadenas de en cualquier orden da una supercuerda trivial de . Una cadena que contiene todas las posibles permutaciones de un conjunto de caracteres específico se denomina superpermutación .
Ver también
Referencias
- ↑ a b c Lothaire, M. (1997). Combinatoria de palabras . Cambridge: Cambridge University Press. ISBN 0-521-59924-5.
- ^ Kelley, Dean (1995). Autómatas y lenguajes formales: una introducción . Londres: Prentice-Hall International. ISBN 0-13-497777-7.
- ^ 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
- Medios relacionados con la subcadena en Wikimedia Commons