Subcadena

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, " the best of " es una subcadena de " It was the best of times ". En cambio, " 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${\displaystyle S}$es una subcadena de${\displaystyle S}$que ocurre al principio de${\displaystyle S}$; asimismo, un sufijo de una cadena${\displaystyle S}$es una subcadena que aparece al final de${\displaystyle S}$.

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

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

Ejemplo: La cadena${\displaystyle u={\texttt {ana}}}$es igual a subcadenas (y subsecuencias) de${\displaystyle t={\texttt {plátano}}}$en dos desplazamientos diferentes:

banana ||||| Ana|| ||| Ana

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

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${\displaystyle u}$es una subcadena de${\displaystyle t}$También se trata de una subsecuencia , un concepto más general. Las ocurrencias de un patrón determinado en una cadena dada se pueden encontrar mediante 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).

Una cuerda${\displaystyle p}$es un prefijo ^{[ 1 ]} de una cadena${\displaystyle t}$si existe una cadena${\displaystyle s}$de tal manera que${\displaystyle t=ps}$. 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 ser vacío. Un prefijo puede verse como un caso especial de una subcadena.

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${\displaystyle p\sqsubseteq t}$indica que${\displaystyle p}$es un prefijo de${\displaystyle t}$. Esto define una relación binaria en cadenas, llamada relación de prefijo , que es un tipo particular de orden de prefijo .

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

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 de tipo trie que representa todos sus sufijos. Los árboles de sufijos tienen numerosas aplicaciones en algoritmos de cadenas . El array 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.

Un borde es un sufijo y un prefijo de la misma cadena, por ejemplo "${\displaystyle {\texttt {bab}}}$" es una frontera de "${\displaystyle {\texttt {babab}}}$" (y también de "${\displaystyle {\texttt {baboon}}\,\,{\texttt {eating}}\,\,{\texttt {a}}\,\,{\texttt {kebab}}}$").

Una supercadena de un conjunto finito${\displaystyle P}$de cadenas es una sola cadena que contiene todas las cadenas en${\displaystyle P}$como una subcadena. Por ejemplo,${\displaystyle {\texttt {bclabccefab}}}$es una supercadena de${\displaystyle P=\{{\texttt {abcc}},{\texttt {efab}},{\texttt {bccla}}\}}$, y${\displaystyle {\texttt {efabccla}}}$es uno más corto. Concatenando todos los miembros de${\displaystyle P}$, en orden arbitrario, siempre obtiene una supercadena trivial de${\displaystyle P}$Encontrar supercuerdas cuya longitud sea lo más pequeña posible es un problema más interesante.

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

• Índice de subcadena
• autómata de sufijo