Subcadena

Parte contigua de una secuencia de símbolos.

" cadena " es una subcadena de " subcadena "

En teoría del lenguaje formal e informática , una subcadena es una secuencia contigua de caracteres dentro de una cadena . ^{[ cita necesaria ]} Por ejemplo, " lo mejor de " es una subcadena de " Fue el mejor de los tiempos ". Por el contrario, " 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 aparece al principio de ; Asimismo, un sufijo de una cadena es una subcadena que aparece al final de . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

Las subcadenas de la cadena " apple " serían: " a ", " ap ", " app ", " appl ", " appl " , " p ", " pp ", " ppl ", " pple ", " pl " , " ple ", " l ", " le " " e ", "" (tenga en cuenta la cadena vacía al final).

Subcadena

Una cadena 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. ${\displaystyle u}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle s}$ ${\displaystyle t=pus}$

Ejemplo: la cadena es igual a subcadenas (y subsecuencias) de en dos desplazamientos diferentes: ${\displaystyle u=}$ana ${\displaystyle t=}$banana

banana ||||| ana|| ||| ana

La primera aparición se obtiene con y , mientras que la segunda aparición se obtiene con y siendo la cadena vacía. ${\displaystyle p=}$b ${\displaystyle s=}$na ${\displaystyle p=}$ban ${\displaystyle s}$

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, nanes 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 apariciones de un patrón determinado en una cadena determinada 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 problema de subcadena común más larga . En la literatura matemática, las subcadenas también se denominan subpalabras (en Estados Unidos) o factores (en Europa). ^{[ cita necesaria ]} ${\displaystyle u}$ ${\displaystyle t}$

Prefijo

Una cadena 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 misma; ^[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. ${\displaystyle p}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t=ps}$

Ejemplo: la cadena banes igual a un prefijo (y subcadena y subsecuencia) de la cadena banana:

banana|||prohibición

El símbolo de subconjunto cuadrado se usa a veces para indicar un prefijo, por lo que indica 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 . ${\displaystyle p\sqsubseteq t}$ ${\displaystyle p}$ ${\displaystyle t}$

Sufijo

Una cadena es un sufijo ^[1] de una cadena si existe una cadena tal que . Un sufijo adecuado de una cadena no es igual a la cadena misma. Una interpretación más restringida es que tampoco está vacío. ^[1] Un sufijo puede verse como un caso especial de una subcadena. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle t=ps}$

Ejemplo: la cadena nanaes igual a un sufijo (y subcadena y subsecuencia) de la cadena banana:

banana |||| nana

Un árbol de sufijos para una cadena es una estructura de datos trie que representa todos sus sufijos. Los árboles de sufijos tienen una gran cantidad 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.

Borde

Un borde es un sufijo y un prefijo de la misma cadena, por ejemplo, "bab" es un borde de "babab" (y también de "babuino comiendo un kebab"). ^{[ cita necesaria ]}

supercuerda

Una supercadena de un conjunto finito de cadenas es una cadena única que contiene cada cadena como una subcadena. Por ejemplo, es una supercadena de y es más corta. Al concatenar todos los miembros de , en orden arbitrario, siempre se obtiene una supercadena trivial de . Encontrar supercuerdas cuya longitud sea lo más pequeña posible es un problema más interesante. ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle {\text{bcclabccefab}}}$ ${\displaystyle P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}}$ ${\displaystyle {\text{efabccla}}}$ ${\displaystyle P}$ ${\displaystyle P}$

Una cadena que contiene todas las permutaciones posibles de un conjunto de caracteres específico se denomina superpermutación .

Ver también

• Notación de llaves
• Índice de subcadena
• autómata sufijo

Referencias

1. Lothaire, M. (1997). Combinatoria sobre palabras . Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-59924-5.
2. Kelley, decano (1995). Autómatas y lenguajes formales: una introducción . Londres: Prentice-Hall Internacional. ISBN 0-13-497777-7.
3. 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.