Cadena (informática)

En programación informática , una cadena es tradicionalmente una secuencia de caracteres , ya sea como una constante literal o como algún tipo de variable . Esta última puede permitir que sus elementos se modifiquen y se cambie la longitud, o puede ser fija (después de la creación). Una cadena se considera generalmente como un tipo de datos y a menudo se implementa como una estructura de datos de matriz de bytes (o palabras ) que almacena una secuencia de elementos, normalmente caracteres, utilizando alguna codificación de caracteres . Cadena también puede denotar matrices más generales u otros tipos y estructuras de datos de secuencia (o lista ).

Dependiendo del lenguaje de programación y del tipo de datos preciso utilizado, una variable declarada como cadena puede provocar que el almacenamiento en la memoria se asigne estáticamente para una longitud máxima predeterminada o emplear una asignación dinámica para permitirle contener una cantidad variable de elementos.

Cuando una cadena aparece literalmente en el código fuente , se conoce como una cadena literal o una cadena anónima. ^[1]

En los lenguajes formales , que se utilizan en la lógica matemática y la informática teórica , una cadena es una secuencia finita de símbolos que se eligen de un conjunto llamado alfabeto .

Un propósito principal de las cadenas es almacenar texto legible para humanos, como palabras y oraciones. Las cadenas se utilizan para comunicar información desde un programa de computadora al usuario del programa. ^[2] Un programa también puede aceptar la entrada de cadenas de su usuario. Además, las cadenas pueden almacenar datos expresados ​​como caracteres pero no destinados a la lectura humana.

Cadenas de ejemplo y sus propósitos:

• Un mensaje como " file upload complete" es una cadena que el software muestra a los usuarios finales . En el código fuente del programa , este mensaje probablemente aparecería como una cadena literal .
• Texto ingresado por el usuario, como " I got a new job today" como una actualización de estado en un servicio de redes sociales . En lugar de una cadena literal, el software probablemente almacenaría esta cadena en una base de datos .
• Datos alfabéticos, como " AGATGCCGT" que representan secuencias de ácidos nucleicos del ADN . ^[3]
• Parámetros o configuraciones de la computadora, como " ?action=edit" como cadena de consulta de URL . A menudo, estos están pensados ​​para que sean legibles para los humanos, aunque su propósito principal es comunicarse con las computadoras.

El término cadena también puede designar una secuencia de datos o registros informáticos distintos de caracteres —como una "cadena de bits "— pero cuando se utiliza sin ninguna calificación se refiere a cadenas de caracteres. ^[4]

El uso de la palabra "cadena" para referirse a cualquier elemento dispuesto en una línea, serie o sucesión se remonta a siglos atrás. ^{[5] [6]} En la composición tipográfica del siglo XIX, los cajistas usaban el término "cadena" para indicar la longitud de un tipo impreso en papel; la cadena se medía para determinar el salario del cajista. ^{[7] [4] [8]}

El uso de la palabra "cadena" para significar "una secuencia de símbolos o elementos lingüísticos en un orden definido" surgió de las matemáticas, la lógica simbólica y la teoría lingüística para hablar sobre el comportamiento formal de los sistemas simbólicos, dejando de lado el significado de los símbolos. ^[4]

Por ejemplo, el lógico CI Lewis escribió en 1918: ^[9]

Un sistema matemático es cualquier conjunto de cadenas de signos reconocibles en el que algunas de las cadenas se toman inicialmente y el resto se deriva de ellas mediante operaciones realizadas según reglas que son independientes de cualquier significado asignado a los signos. Que un sistema esté formado por «signos» en lugar de sonidos u olores es irrelevante.

Según Jean E. Sammet , "el primer lenguaje realista de manejo de cadenas y comparación de patrones" para computadoras fue COMIT en la década de 1950, seguido por el lenguaje SNOBOL a principios de la década de 1960. ^[10]

Un tipo de datos de cadena es un tipo de datos modelado sobre la idea de una cadena formal. Las cadenas son un tipo de datos tan importante y útil que se implementan en casi todos los lenguajes de programación . En algunos lenguajes están disponibles como tipos primitivos y en otros como tipos compuestos . La sintaxis de la mayoría de los lenguajes de programación de alto nivel permite que una cadena, generalmente entre comillas de alguna manera, represente una instancia de un tipo de datos de cadena; una metacadena de este tipo se denomina literal o literal de cadena .

Aunque las cadenas formales pueden tener una longitud finita arbitraria, la longitud de las cadenas en lenguajes reales a menudo está restringida a un máximo artificial. En general, hay dos tipos de tipos de datos de cadena: cadenas de longitud fija , que tienen una longitud máxima fija que se determina en tiempo de compilación y que utilizan la misma cantidad de memoria independientemente de si se necesita este máximo o no, y cadenas de longitud variable , cuya longitud no está fijada arbitrariamente y que pueden utilizar cantidades variables de memoria según los requisitos reales en tiempo de ejecución (consulte Gestión de memoria ). La mayoría de las cadenas en los lenguajes de programación modernos son cadenas de longitud variable. Por supuesto, incluso las cadenas de longitud variable están limitadas en longitud, por el tamaño de la memoria de computadora disponible . La longitud de la cadena se puede almacenar como un entero separado (que puede poner otro límite artificial en la longitud) o implícitamente a través de un carácter de terminación, generalmente un valor de carácter con todos los bits cero como en el lenguaje de programación C. Consulte también "Terminación nula" a continuación.

Históricamente, los tipos de datos de cadena asignaban un byte por carácter y, aunque el conjunto exacto de caracteres variaba según la región, las codificaciones de caracteres eran lo suficientemente similares como para que los programadores pudieran a menudo ignorar esto, ya que los caracteres que un programa trataba de manera especial (como el punto, el espacio y la coma) estaban en el mismo lugar en todas las codificaciones que encontraría un programa. Estos conjuntos de caracteres se basaban típicamente en ASCII o EBCDIC . Si el texto en una codificación se mostraba en un sistema que usaba una codificación diferente, el texto a menudo se distorsionaba , aunque a menudo era algo legible y algunos usuarios de computadoras aprendieron a leer el texto distorsionado.

Los idiomas logográficos como el chino , el japonés y el coreano (conocidos colectivamente como CJK ) necesitan mucho más de 256 caracteres (el límite de una codificación de un byte de 8 bits por carácter) para una representación razonable. Las soluciones normales implicaban mantener representaciones de un solo byte para ASCII y usar representaciones de dos bytes para los ideogramas CJK . El uso de estos con el código existente condujo a problemas con la coincidencia y el corte de cadenas, cuya gravedad dependía de cómo se diseñara la codificación de caracteres. Algunas codificaciones como la familia EUC garantizan que un valor de byte en el rango ASCII representará solo ese carácter ASCII, lo que hace que la codificación sea segura para los sistemas que usan esos caracteres como separadores de campo. Otras codificaciones como ISO-2022 y Shift-JIS no ofrecen tales garantías, lo que hace que la coincidencia en códigos de bytes sea insegura. Estas codificaciones tampoco eran "autosincronizables", por lo que para localizar los límites de los caracteres era necesario retroceder hasta el inicio de una cadena, y pegar dos cadenas juntas podía provocar la corrupción de la segunda cadena.

Unicode ha simplificado un poco el panorama. La mayoría de los lenguajes de programación tienen ahora un tipo de datos para las cadenas Unicode. El formato de flujo de bytes preferido de Unicode, UTF-8, está diseñado para no tener los problemas descritos anteriormente para las codificaciones multibyte más antiguas. UTF-8, UTF-16 y UTF-32 requieren que el programador sepa que las unidades de código de tamaño fijo son diferentes de los "caracteres", la principal dificultad actual son las API diseñadas incorrectamente que intentan ocultar esta diferencia (UTF-32 hace que los puntos de código sean de tamaño fijo, pero estos no son "caracteres" debido a la composición de los códigos).

Algunos lenguajes, como C++ , Perl y Ruby , normalmente permiten cambiar el contenido de una cadena después de haberla creado; estas se denominan cadenas mutables . En otros lenguajes, como Java , JavaScript , Lua , Python y Go , el valor es fijo y se debe crear una nueva cadena si se va a realizar alguna alteración; estas se denominan cadenas inmutables . Algunos de estos lenguajes con cadenas inmutables también proporcionan otro tipo que es mutable, como Java y .NETStringBuilder , Java seguro para subprocesos StringBuffery Cocoa NSMutableString . La inmutabilidad tiene ventajas y desventajas: aunque las cadenas inmutables pueden requerir la creación ineficiente de muchas copias, son más simples y completamente seguras para subprocesos .

Las cadenas se implementan normalmente como matrices de bytes, caracteres o unidades de código, con el fin de permitir un acceso rápido a unidades individuales o subcadenas, incluidos los caracteres cuando tienen una longitud fija. Algunos lenguajes, como Haskell, las implementan como listas enlazadas .

Algunos lenguajes, como Prolog y Erlang , evitan implementar un tipo de datos de cadena dedicado, y en su lugar adoptan la convención de representar cadenas como listas de códigos de caracteres.

Las representaciones de cadenas dependen en gran medida de la elección del repertorio de caracteres y del método de codificación de caracteres. Las implementaciones de cadenas más antiguas se diseñaron para funcionar con el repertorio y la codificación definidos por ASCII o extensiones más recientes como la serie ISO 8859. Las implementaciones modernas suelen utilizar el amplio repertorio definido por Unicode junto con una variedad de codificaciones complejas como UTF-8 y UTF-16.

El término cadena de bytes suele indicar una cadena de bytes de uso general, en lugar de cadenas de solo caracteres (legibles), cadenas de bits o similares. Las cadenas de bytes suelen implicar que los bytes pueden tomar cualquier valor y que cualquier dato se puede almacenar tal como está, lo que significa que no debe haber ningún valor que se interprete como un valor de terminación.

La mayoría de las implementaciones de cadenas son muy similares a las matrices de longitud variable , en las que las entradas almacenan los códigos de caracteres de los caracteres correspondientes. La principal diferencia es que, con ciertas codificaciones, un solo carácter lógico puede ocupar más de una entrada en la matriz. Esto sucede, por ejemplo, con UTF-8, donde los códigos individuales ( puntos de código UCS ) pueden ocupar entre uno y cuatro bytes, y los caracteres individuales pueden ocupar una cantidad arbitraria de códigos. En estos casos, la longitud lógica de la cadena (número de caracteres) difiere de la longitud física de la matriz (número de bytes en uso). UTF-32 evita la primera parte del problema.

La longitud de una cadena se puede almacenar de forma implícita utilizando un carácter de terminación especial; a menudo, este es el carácter nulo (NUL), que tiene todos los bits cero, una convención utilizada y perpetuada por el popular lenguaje de programación C. [ ^11] Por lo tanto, esta representación se conoce comúnmente como una cadena C. Esta representación de una cadena de n caracteres ocupa n + 1 espacio (1 para el terminador) y, por lo tanto, es una estructura de datos implícita .

En cadenas terminadas, el código de terminación no es un carácter permitido en ninguna cadena. Las cadenas con campo de longitud no tienen esta limitación y también pueden almacenar datos binarios arbitrarios .

Un ejemplo de una cadena terminada en nulo almacenada en un búfer de 10 bytes , junto con su representación ASCII (o más moderna , UTF-8 ) como números hexadecimales de 8 bits es:

La longitud de la cadena del ejemplo anterior, " FRANK", es de 5 caracteres, pero ocupa 6 bytes. Los caracteres que aparecen después del terminador no forman parte de la representación; pueden ser parte de otros datos o simplemente basura. (Las cadenas de este formato a veces se denominan cadenas ASCIZ , por la directiva original del lenguaje ensamblador que se utilizaba para declararlas).

El uso de un byte especial distinto de nulo para terminar cadenas ha aparecido históricamente tanto en hardware como en software, aunque a veces con un valor que también era un carácter de impresión. $fue utilizado por muchos sistemas ensambladores, :utilizado por sistemas CDC (este carácter tenía un valor de cero) y el ZX80 utilizó "^[12] ya que este era el delimitador de cadena en su lenguaje BASIC.

Las máquinas de "procesamiento de datos" similares, como la IBM 1401, utilizaban un bit especial de marca de palabra para delimitar las cadenas por la izquierda, donde la operación comenzaría por la derecha. Este bit tenía que estar claro en todas las demás partes de la cadena. Esto significaba que, si bien la IBM 1401 tenía una palabra de siete bits, a casi nadie se le ocurrió utilizar esto como una característica y anular la asignación del séptimo bit para (por ejemplo) manejar códigos ASCII.

Los primeros programas informáticos para microordenadores se basaban en el hecho de que los códigos ASCII no utilizan el bit de orden superior y lo configuran para indicar el final de una cadena. Debe restablecerse a 0 antes de la salida. ^[13]

La longitud de una cadena también se puede almacenar explícitamente, por ejemplo, anteponiendo la cadena con la longitud como valor de byte. Esta convención se utiliza en muchos dialectos de Pascal ; como consecuencia, algunas personas denominan a este tipo de cadena cadena Pascal o P-string . El almacenamiento de la longitud de la cadena como byte limita la longitud máxima de la cadena a 255. Para evitar tales limitaciones, las implementaciones mejoradas de P-strings utilizan palabras de 16, 32 o 64 bits para almacenar la longitud de la cadena. Cuando el campo de longitud cubre el espacio de direcciones , las cadenas están limitadas solo por la memoria disponible .

Si la longitud está limitada, entonces se puede codificar en un espacio constante, típicamente una palabra de máquina, lo que conduce a una estructura de datos implícita , que toma el espacio n + k , donde k es el número de caracteres en una palabra (8 para ASCII de 8 bits en una máquina de 64 bits, 1 para UTF-32/UCS-4 de 32 bits en una máquina de 32 bits, etc.). Si la longitud no está limitada, la codificación de una longitud n toma el espacio log( n ) (ver código de longitud fija ), por lo que las cadenas con prefijo de longitud son una estructura de datos sucinta , que codifica una cadena de longitud n en el espacio log( n ) + n .

En el último caso, el campo de prefijo de longitud en sí no tiene una longitud fija, por lo tanto, los datos de la cadena real deben moverse cuando la cadena crece de tal manera que es necesario aumentar el campo de longitud.

Aquí hay una cadena Pascal almacenada en un búfer de 10 bytes, junto con su representación ASCII / UTF-8:

Muchos lenguajes, incluidos los orientados a objetos, implementan cadenas como registros con una estructura interna como:

clase cadena { tamaño_t longitud ; char * texto ; };      

Sin embargo, dado que la implementación suele estar oculta , se debe acceder a la cadena y modificarla a través de funciones miembro. textes un puntero a un área de memoria asignada dinámicamente, que se puede expandir según sea necesario. Véase también cadena (C++) .

Tanto los códigos de longitud como los de terminación de caracteres limitan las cadenas: por ejemplo, las matrices de caracteres C que contienen caracteres nulos (NUL) no pueden manejarse directamente mediante funciones de la biblioteca de cadenas C : las cadenas que utilizan un código de longitud están limitadas al valor máximo del código de longitud.

Ambas limitaciones se pueden superar mediante una programación inteligente.

Es posible crear estructuras de datos y funciones que las manipulen sin los problemas asociados con la terminación de caracteres y que, en principio, puedan superar los límites de longitud del código. También es posible optimizar la cadena representada utilizando técnicas de codificación de longitud de ejecución (reemplazando caracteres repetidos por el valor del carácter y una longitud) y codificación Hamming ^{[ aclaración necesaria ]} .

Si bien estas representaciones son comunes, otras son posibles. El uso de cuerdas hace que ciertas operaciones con cadenas, como inserciones, eliminaciones y concatenaciones, sean más eficientes.

La estructura de datos principal de un editor de texto es la que administra la cadena (secuencia de caracteres) que representa el estado actual del archivo que se está editando. Si bien ese estado podría almacenarse en una única matriz larga y consecutiva de caracteres, un editor de texto típico utiliza en cambio una representación alternativa como su estructura de datos de secuencia (un búfer de espacios , una lista enlazada de líneas, una tabla de piezas o una cuerda ), lo que hace que ciertas operaciones de cadena, como inserciones, eliminaciones y deshacer ediciones anteriores, sean más eficientes. ^[14]

La diferente distribución de la memoria y los requisitos de almacenamiento de las cadenas pueden afectar la seguridad del programa que accede a los datos de la cadena. Las representaciones de cadenas que requieren un carácter de terminación suelen ser susceptibles a problemas de desbordamiento de búfer si el carácter de terminación no está presente, debido a un error de codificación o a que un atacante altera deliberadamente los datos. Las representaciones de cadenas que adoptan un campo de longitud independiente también son susceptibles si la longitud se puede manipular. En tales casos, el código del programa que accede a los datos de la cadena requiere una comprobación de límites para garantizar que no acceda o cambie inadvertidamente datos fuera de los límites de memoria de la cadena.

Los datos de cadena se obtienen con frecuencia a partir de la entrada del usuario a un programa. Por lo tanto, es responsabilidad del programa validar la cadena para garantizar que represente el formato esperado. Realizar una validación limitada o nula de la entrada del usuario puede hacer que un programa sea vulnerable a ataques de inyección de código .

A veces, es necesario incrustar cadenas dentro de un archivo de texto que sea legible para humanos y que esté destinado a ser utilizado por una máquina. Esto es necesario, por ejemplo, en el código fuente de lenguajes de programación o en archivos de configuración. En este caso, el carácter NUL no funciona bien como terminador, ya que normalmente es invisible (no se puede imprimir) y es difícil de introducir mediante un teclado. Almacenar la longitud de la cadena también sería un inconveniente, ya que el cálculo y el seguimiento manual de la longitud son tediosos y propensos a errores.

Dos representaciones comunes son:

• Entre comillas ( comillas dobles ASCII 0x22"str" o comillas simples ASCII 0x27 'str'), utilizadas por la mayoría de los lenguajes de programación. Para poder incluir caracteres especiales como las propias comillas, caracteres de nueva línea o caracteres no imprimibles, suelen estar disponibles secuencias de escape , normalmente precedidas por el carácter de barra invertida (ASCII 0x5C).
• Terminado por una secuencia de nueva línea , por ejemplo en archivos INI de Windows .

Si bien las cadenas de caracteres son usos muy comunes de las cadenas, una cadena en informática puede referirse genéricamente a cualquier secuencia de datos tipificados de manera homogénea. Una cadena de bits o una cadena de bytes , por ejemplo, se puede utilizar para representar datos binarios no textuales recuperados de un medio de comunicación. Estos datos pueden o no estar representados por un tipo de datos específico de cadena, según las necesidades de la aplicación, el deseo del programador y las capacidades del lenguaje de programación que se utilice. Si la implementación de la cadena del lenguaje de programación no es de 8 bits , se pueden producir daños en los datos.

Los programadores de C hacen una clara distinción entre una "cadena", también conocida como "cadena de caracteres", que por definición siempre termina en cero, y una "cadena de bytes" o "pseudocadena", que puede almacenarse en la misma matriz pero que a menudo no termina en cero. El uso de funciones de manejo de cadenas de C en una "cadena de bytes" de este tipo a menudo parece funcionar, pero más tarde conduce a problemas de seguridad. ^{[15] [16] [17]}

Existen muchos algoritmos para procesar cadenas, cada uno con distintas ventajas y desventajas. Los algoritmos en competencia pueden analizarse en función del tiempo de ejecución, los requisitos de almacenamiento, etc. El nombre stringología fue acuñado en 1984 por el científico informático Zvi Galil para referirse a la teoría de algoritmos y estructuras de datos utilizadas para el procesamiento de cadenas. ^{[18] [19] [20]}

Algunas categorías de algoritmos incluyen:

• Algoritmos de búsqueda de cadenas para encontrar una subcadena o patrón determinado
• Algoritmos de manipulación de cadenas
• Algoritmos de ordenamiento
• Algoritmos de expresiones regulares
• Analizando una cadena
• Minería de secuencias

Los algoritmos de cadenas avanzados a menudo emplean mecanismos y estructuras de datos complejos, entre ellos árboles de sufijos y máquinas de estados finitos .

Las cadenas de caracteres son un tipo de datos tan útil que se han diseñado varios lenguajes para facilitar la escritura de aplicaciones de procesamiento de cadenas. Algunos ejemplos son los siguientes:

• AWK
• Icono
• PAPERAS
• Perl
• Rexx
• Rubí
• sed
• SNOBOL
• Tcl
• TTM

Muchas utilidades de Unix realizan manipulaciones de cadenas simples y se pueden usar para programar fácilmente algunos algoritmos de procesamiento de cadenas potentes. Los archivos y los flujos finitos se pueden considerar cadenas.

Algunas API como Multimedia Control Interface , SQL integrado o printf utilizan cadenas para contener comandos que serán interpretados.

Muchos lenguajes de programación , incluidos Perl, Python , Ruby y Tcl, emplean expresiones regulares para facilitar las operaciones con texto. Perl es particularmente conocido por su uso de expresiones regulares, ^[21] y muchos otros lenguajes y aplicaciones implementan expresiones regulares compatibles con Perl .

Algunos lenguajes como Perl y Ruby admiten la interpolación de cadenas , lo que permite evaluar expresiones arbitrarias e incluirlas en literales de cadena.

Las funciones de cadena se utilizan para crear cadenas o cambiar el contenido de una cadena mutable. También se utilizan para consultar información sobre una cadena. El conjunto de funciones y sus nombres varía según el lenguaje de programación de la computadora .

El ejemplo más básico de una función de cadena es la función de longitud de cadenalength , que devuelve la longitud de una cadena (sin contar los caracteres de terminación ni la información estructural interna de la cadena) y no modifica la cadena. Esta función suele llamarse o len. Por ejemplo, length("hello world")devolvería 11. Otra función común es la concatenación , donde se crea una nueva cadena añadiendo dos cadenas, a menudo se trata del operador de adición + .

Algunas arquitecturas de conjuntos de instrucciones de microprocesadores contienen soporte directo para operaciones de cadena, como copia de bloques (por ejemplo, en Intel x86m ). ^[22] REPNZ MOVSB

Sea Σ un conjunto finito de símbolos distintos e inequívocos (alternativamente llamados caracteres), llamado alfabeto . Una cadena (o palabra ^[23] o expresión ^{[24] ) sobre Σ es cualquier} secuencia finita de símbolos a partir de Σ. ^[25] Por ejemplo, si Σ = {0, 1}, entonces 01011 es una cadena sobre Σ.

La longitud de una cadena s es el número de símbolos en s (la longitud de la secuencia) y puede ser cualquier entero no negativo ; a menudo se denota como | s |. La cadena vacía es la única cadena sobre Σ de longitud 0, y se denota ε o λ . ^{[25] [26]}

El conjunto de todas las cadenas de caracteres de longitud n que tengan más de Σ se denota por Σ ⁿ . Por ejemplo, si Σ = {0, 1}, entonces Σ ² = {00, 01, 10, 11}. Tenemos Σ ⁰ = {ε} para cada alfabeto Σ.

El conjunto de todas las cadenas sobre Σ de cualquier longitud es la clausura de Kleene de Σ y se denota Σ ^* . En términos de Σ ⁿ ,

${\displaystyle \Sigma ^{*}=\bigcup _{n\in \mathbb {N} \cup \{0\}}\Sigma ^{n}}$

Por ejemplo, si Σ = {0, 1}, entonces Σ ^* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Aunque el conjunto Σ ^* en sí mismo es infinito contable , cada elemento de Σ ^* es una cadena de longitud finita.

Un conjunto de cadenas sobre Σ (es decir, cualquier subconjunto de Σ ^* ) se denomina lenguaje formal sobre Σ. Por ejemplo, si Σ = {0, 1}, el conjunto de cadenas con un número par de ceros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, es un lenguaje formal sobre Σ.

La concatenación es una operación binaria importante en Σ ^* . Para dos cadenas cualesquiera s y t en Σ ^* , su concatenación se define como la secuencia de símbolos en s seguida de la secuencia de caracteres en t , y se denota st . Por ejemplo, si Σ = {a, b, ..., z}, s  = bear, y t  = hug, entonces st  = bearhugy ts  = hugbear.

La concatenación de cadenas es una operación asociativa , pero no conmutativa . La cadena vacía ε sirve como elemento identidad ; para cualquier cadena s , ε s = s ε = s . Por lo tanto, el conjunto Σ ^* y la operación de concatenación forman un monoide , el monoide libre generado por Σ. Además, la función length define un homomorfismo de monoide desde Σ ^* hasta los números enteros no negativos (es decir, una función , tal que ).${\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}}$${\displaystyle L(st)=L(s)+L(t)\quad \para todo s,t\en \Sigma ^{*}}$

Se dice que una cadena s es una subcadena o factor de t si existen cadenas u y v (posiblemente vacías) tales que t = usv . La relación "es una subcadena de" define un orden parcial en Σ ^* , cuyo elemento menor es la cadena vacía.

Se dice que una cadena s es un prefijo de t si existe una cadena u tal que t = su . Si u no está vacía, se dice que s es un prefijo propio de t . Simétricamente, se dice que una cadena s es un sufijo de t si existe una cadena u tal que t = us . Si u no está vacía, se dice que s es un sufijo propio de t . Los sufijos y prefijos son subcadenas de t . Ambas relaciones "es un prefijo de" y "es un sufijo de" son órdenes de prefijo .

El reverso de una cadena es una cadena con los mismos símbolos pero en orden inverso. Por ejemplo, si s = abc (donde a, b y c son símbolos del alfabeto), entonces el reverso de s es cba. Una cadena que es el reverso de sí misma (por ejemplo, s = madam) se denomina palíndromo , que también incluye la cadena vacía y todas las cadenas de longitud 1.

Se dice que una cadena s = uv es una rotación de t si t = vu . Por ejemplo, si Σ = {0, 1} la cadena 0011001 es una rotación de 0100110, donde u = 00110 y v = 01. Como otro ejemplo, la cadena abc tiene tres rotaciones diferentes, a saber, la propia abc (con u = abc, v = ε), bca (con u = bc, v = a) y cab (con u = c, v = ab).

A menudo resulta útil definir un ordenamiento en un conjunto de cadenas. Si el alfabeto Σ tiene un orden total (cf. orden alfabético ) se puede definir un orden total en Σ ^* llamado orden lexicográfico . El orden lexicográfico es total si el orden alfabético lo es, pero no está bien fundamentado para ningún alfabeto no trivial, incluso si el orden alfabético lo es. Por ejemplo, si Σ = {0, 1} y 0 < 1, entonces el orden lexicográfico en Σ ^* incluye las relaciones ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 1111 < ... < 11111 ... Con respecto a este ordenamiento, por ejemplo, el conjunto infinito { 1, 01, 001, 0001, 00001, 000001, ... } no tiene ningún elemento mínimo.

Consulte Shortlex para obtener un ordenamiento de cadenas alternativo que preserva la buena fundamentación. Para el alfabeto de ejemplo, el orden de Shortlex es ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 < ... < 1111 < 00000 < 00001 ...

En la teoría formal se producen con frecuencia otras operaciones adicionales sobre cadenas. Estas se describen en el artículo sobre operaciones con cadenas .

Las cadenas admiten la siguiente interpretación como nodos en un gráfico, donde k es el número de símbolos en Σ:

• Las cadenas de longitud fija de longitud n pueden verse como las ubicaciones de números enteros en un hipercubo de dimensión n con lados de longitud k -1.
• Las cadenas de longitud variable (de longitud finita) pueden verse como nodos en un árbol k -ario perfecto .
• Las cadenas infinitas (que de otro modo no se considerarían aquí) pueden verse como caminos infinitos en un gráfico completo de k nodos .

La topología natural en el conjunto de cadenas de longitud fija o de longitud variable es la topología discreta, pero la topología natural en el conjunto de cadenas infinitas es la topología límite , que considera el conjunto de cadenas infinitas como el límite inverso de los conjuntos de cadenas finitas. Esta es la construcción utilizada para los números p -ádicos y algunas construcciones del conjunto de Cantor , y produce la misma topología.

Los isomorfismos entre representaciones de cadenas de topologías se pueden encontrar normalizando de acuerdo con la rotación de cadena lexicográficamente mínima .

• Seguridad binaria : una propiedad de las funciones de manipulación de cadenas que tratan su entrada como un flujo de datos sin procesar
• Matriz de bits : una cadena de dígitos binarios
• Manejo de cuerdas en C : descripción general del manejo de cuerdas en C
• Manejo de cadenas en C++ : descripción general del manejo de cadenas en C++
• Comparación de lenguajes de programación (funciones de cadena)
• Cadena de conexión : se pasa a un controlador para iniciar una conexión (por ejemplo, a una base de datos)
• Cadena vacía : sus propiedades y representación en lenguajes de programación
• Cadena incompresible : una cadena que no se puede comprimir mediante ningún algoritmo.
• Cuerda (estructura de datos) : una estructura de datos para manipular eficientemente cadenas largas
• Métrica de cadenas : nociones de similitud entre cadenas