Subcadena

Parte contigua de una secuencia de símbolos

En la teoría del lenguaje formal y la informática , una subcadena es una secuencia contigua de caracteres dentro de una cadena . ^{[ cita requerida ]} Por ejemplo, " the best of " es una subcadena de " It was the best of times ". 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 ; de la misma manera, un sufijo de una cadena es una subcadena que aparece al final de . ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$ ${\estilo de visualización S}$

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

Subcadena

Una cadena es una subcadena (o factor) ^[1] de una cadena si existen dos cadenas y tales que . En particular, la cadena vacía es una subcadena de cada cadena. ${\estilo de visualización u}$ ${\estilo de visualización t}$ ${\estilo de visualización p}$ ${\estilo de visualización s}$ $t=pus$

Ejemplo: La cadena es igual a subcadenas (y subsecuencias) de en dos desplazamientos diferentes: ${\estilo de visualización u=}$ ana ${\estilo de visualización 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. ${\estilo de visualización p=}$ b ${\estilo de visualización s=}$ na ${\estilo de visualización p=}$ ban ${\estilo de visualización s}$

Una subcadena de una cadena es un prefijo de un sufijo de la cadena y, equivalentemente, 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 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 Estados Unidos) o factores (en Europa). ^[^{cita requerida}^] ${\estilo de visualización u}$ ${\estilo de visualización t}$

Prefijo

Una cadena es un prefijo ^[1] de una cadena si existe una cadena tal que . Un prefijo propio de una cadena no es igual a la cadena misma; ^[2] algunas fuentes ^[3] además restringen un prefijo propio a no estar vacío. Un prefijo puede verse como un caso especial de una subcadena. ${\estilo de visualización p}$ ${\estilo de visualización t}$ ${\estilo de visualización s}$ $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 utiliza a veces para indicar un prefijo, de modo 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 . $p\sqsubseteq t$ ${\estilo de visualización p}$ ${\estilo de visualización t}$

Sufijo

Una cadena es un sufijo ^[1] de una cadena si existe una cadena tal que . Un sufijo propio 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. ${\estilo de visualización s}$ ${\estilo de visualización t}$ ${\estilo de visualización p}$ $t=ps$

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

banana |||| abuela

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 prefijo de la misma cadena, p. ej., "bab" es un borde de "babab" (y también de "babuino comiendo un kebab"). ^{[ cita requerida ]}

Supercuerda

Una supercadena de un conjunto finito de cadenas es una cadena única que contiene todas las cadenas en como subcadenas. Por ejemplo, es una supercadena de y es más corta. Concatenar todos los miembros de , en orden arbitrario, siempre da como resultado una supercadena trivial de . Encontrar supercadenas cuya longitud sea lo más pequeña posible es un problema más interesante. ${\estilo de visualización P}$ ${\estilo de visualización P}$ ${\text{bcclabccefab}}$ $P=\{{\text{abcc}},{\text{efab}},{\text{bccla}}\}$ ${\text{efabccla}}$ ${\estilo de visualización P}$ ${\estilo de visualización P}$

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

Véase también

Referencias

^ abc 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 . EE. UU.: Cambridge University Press. ISBN 0-521-58519-8.

[Lot97-1] Lothaire, M. (1997). Combinatoria de palabras . Cambridge: Cambridge University Press. ISBN 0-521-59924-5.

[Kel95-2] Kelley, Dean (1995). Autómatas y lenguajes formales: una introducción . Londres: Prentice-Hall International. ISBN 0-13-497777-7.

[Gus97-3] Gusfield, Dan (1999) [1997]. Algoritmos sobre cadenas, árboles y secuencias: informática y biología computacional . EE. UU.: Cambridge University Press. ISBN 0-521-58519-8.