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 .
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).
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.
Ejemplo: La cadena es igual a subcadenas (y subsecuencias) de en dos desplazamientos diferentes:anabanana
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.bnaban
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 ]
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.
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 .
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.
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.
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 ]
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.
Una cadena que contiene todas las permutaciones posibles de un conjunto de caracteres especificado se denomina superpermutación .
