Subcadena - Enciclopedia
En la teoría de lenguajes formales 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". Por contraste, "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
S
{\displaystyle S}
es una subcadena de
S
{\displaystyle S}
que ocurre al principio de
S
{\displaystyle S}
; de manera similar, un sufijo de una cadena
S
{\displaystyle S}
es una subcadena que ocurre al final de
S
{\displaystyle S}
.
Las subcadenas de la cadena "apple" serían:
"a", "ap", "app", "appl", "apple",
"p", "pp", "ppl", "pple",
"pl", "ple",
"l", "le"
"e", ""
(notar la cadena vacía al final).
Subcadena
Una cadena
u
{\displaystyle u}
es una subcadena (o factor) de una cadena
t
{\displaystyle t}
si existen dos cadenas
p
{\displaystyle p}
y
s
{\displaystyle s}
tales que
t
=
p
u
s
{\displaystyle t=pus}
. En particular, la cadena vacía es una subcadena de cualquier cadena.
Ejemplo: La cadena
u
{\displaystyle u=}
ana es igual a subcadenas (y subsecuencias) de la cadena
t
{\displaystyle t=}
banana en dos diferentes desplazamientos:
banana
|||||
ana||
|||
ana
La primera ocurrencia se obtiene con
p
{\displaystyle p=}
b y
s
{\displaystyle s=}
na, mientras que la segunda ocurrencia se obtiene con
p
{\displaystyle p=}
ban y
s
{\displaystyle s}
siendo la cadena vacía.
Una subcadena de una cadena es un prefijo de un sufijo de la cadena, y equivalente un sufijo de un prefijo; por ejemplo, nan es un prefijo de nana, que a su vez es un sufijo de banana. Si
u
{\displaystyle u}
es una subcadena de
t
{\displaystyle t}
, también es una subsecuencia, que es un concepto más general. Las ocurrencias de un patrón determinado en una cadena determinada pueden encontrarse 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 del 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).
Prefijo
Una cadena
p
{\displaystyle p}
es un prefijo de una cadena
t
{\displaystyle t}
si existe una cadena
s
{\displaystyle s}
tal que
t
=
p
s
{\displaystyle t=ps}
. Un prefijo propio de una cadena no es igual a la cadena en sí misma; algunas fuentes, además, restringen un prefijo propio a ser no vacío. Un prefijo puede considerarse como un caso especial de una subcadena.
Ejemplo: La cadena ban es igual a un prefijo (y subcadena y subsecuencia) de la cadena banana:
banana
|||
ban
El símbolo del subconjunto cuadrado a veces se utiliza para indicar un prefijo, de manera que
p
{\displaystyle p}
es un prefijo de
t
{\displaystyle t}
. Esto define una relación binaria entre cadenas, llamada la relación de prefijo, que es un tipo particular de orden de prefijo.
Sufijo
Una cadena
s
{\displaystyle s}
es un sufijo de una cadena
t
{\displaystyle t}
si existe una cadena
p
{\displaystyle p}
tal que
t
=
p
s
{\displaystyle t=ps}
. Un sufijo propio de una cadena no es igual a la cadena en sí misma. Una interpretación más restringida es que tampoco es vacía.[1] Un sufijo puede considerarse como un caso especial de una subcadena.
Ejemplo: La cadena nana es 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 un gran número de aplicaciones en los algoritmos de cadena. El array de sufijos es una versión simplificada de esta estructura de datos que lista las posiciones de inicio 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, por ejemplo, "bab" es un borde de "babab" (y también de "baboon eating a kebab").
Supercadena
Una supercadena de un conjunto finito
P
{\displaystyle P}
de cadenas es una única cadena que contiene a cada cadena en
P
{\displaystyle P}
como una subcadena. Por ejemplo,
bcclabccefab
{\displaystyle {\text{bcclabccefab}}}
es una supercadena de
P
{\displaystyle P}
= {
abcc
,
efab
,
bccla
}
, y
efabccla
{\displaystyle {\text{efabccla}}}
es una más corta. Concatenar todos los miembros de
P
{\displaystyle P}
, en orden arbitrario, siempre obtiene una supercadena trivial de
P
{\displaystyle P}
. Encontrar supercadenas cuyas longitudes sean lo más pequeñas 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.
Ver también
Notación de corchetes
Índice de subcadena
Autómata de sufijo
Referencias