String (computer science)

String length

Although formal strings can have an arbitrary finite length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes: fixed-length strings, which have a fixed maximum length to be determined at compile time and which use the same amount of memory whether this maximum is needed or not, and variable-length strings, whose length is not arbitrarily fixed and which can use varying amounts of memory depending on the actual requirements at run time (see Memory management). Most strings in modern programming languages are variable-length strings. Of course, even variable-length strings are limited in length by the amount of available memory. The string length can be stored as a separate integer (which may put another artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero such as in C programming language. See also "Null-terminated" below.

Character encoding

String datatypes have historically allocated one byte per character, and, although the exact character set varied by region, character encodings were similar enough that programmers could often get away with ignoring this, since characters a program treated specially (such as period and space and comma) were in the same place in all the encodings a program would encounter. These character sets were typically based on ASCII or EBCDIC. If text in one encoding was displayed on a system using a different encoding, text was often mangled, though often somewhat readable and some computer users learned to read the mangled text.

Logographic languages such as Chinese, Japanese, and Korean (known collectively as CJK) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK ideographs. Use of these with existing code led to problems with matching and cutting of strings, the severity of which depended on how the character encoding was designed. Some encodings such as the EUC family guarantee that a byte value in the ASCII range will represent only that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as ISO-2022 and Shift-JIS do not make such guarantees, making matching on byte codes unsafe. These encodings also were not "self-synchronizing", so that locating character boundaries required backing up to the start of a string, and pasting two strings together could result in corruption of the second string.

Unicode has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format UTF-8 is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and UTF-32 require the programmer to know that the fixed-size code units are different from the "characters", the main difficulty currently is incorrectly designed APIs that attempt to hide this difference (UTF-32 does make code points fixed-sized, but these are not "characters" due to composing codes).

Implementations

Some languages, such as C++, Perl, and Ruby, normally allow the contents of a string to be changed after it has been created; these are termed mutable strings. In other languages, such as Java, JavaScript, Lua, Python, and Go, the value is fixed and a new string must be created if any alteration is to be made; these are termed immutable strings. Some of these languages with immutable strings also provide another type that is mutable, such as Java and .NET's StringBuilder, the thread-safe Java StringBuffer, and the Cocoa NSMutableString. Immutability brings advantages and disadvantages: while immutable strings may require inefficiently creating many copies, they are simpler and fully thread-safe.

Strings are typically implemented as arrays of bytes, characters, or code units, to allow fast access to individual units or substrings, including characters when they have a fixed length. A few languages such as Haskell implement them as linked lists instead.

Many high-level languages provide strings as a primitive data type, such as JavaScript and PHP, while most others provide them as a composite data type, some with special language support in writing literals, for example, Java and C#.

Some languages, such as C, Prolog and Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes. Even in programming languages having a dedicated string type, strings can usually be iterated as a sequence of character codes, like lists of integers or other values.

Representations

Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the ISO 8859 series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16.

The term byte string usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such. Byte strings often imply that bytes can take any value and any data can be stored as-is, meaning that there should be no value interpreted as a termination value.

Most string implementations are very similar to variable-length arrays with the entries storing the character codes of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens, for example, with UTF-8, where single codes (UCS code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes. In these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use). UTF-32 avoids the first part of the problem.

public final class String {
    private unsigned long length; // string length
    private UniquePointer<char[]> text; // explicit ownership
    
    // public methods...
}

Security concerns

The differing memory layout and storage requirements of strings can affect the security of the program accessing the string data. String representations requiring a terminating character are commonly susceptible to buffer overflow problems if the terminating character is not present, caused by a coding error or an attacker deliberately altering the data. String representations adopting a separate length field are also susceptible if the length can be manipulated. In such cases, program code accessing the string data requires bounds checking to ensure that it does not inadvertently access or change data outside of the string memory limits.

String data is frequently obtained from user input to a program. As such, it is the responsibility of the program to validate the string to ensure that it represents the expected format. Performing limited or no validation of user input can cause a program to be vulnerable to code injection attacks.

Concatenation and substrings

Concatenation is an important binary operation on ${\displaystyle \Sigma ^{*}}$. For any two strings ${\displaystyle s}$ and ${\displaystyle t}$ in ${\displaystyle \Sigma ^{*}}$, their concatenation is defined as the sequence of symbols in ${\displaystyle s}$ followed by the sequence of characters in ${\displaystyle t}$, and is denoted ${\displaystyle st}$. For example, if ${\displaystyle \Sigma =\{{\texttt {a}},{\texttt {b}},...,{\texttt {z}}\}}$ (i.e. the lowercase English alphabet), ${\displaystyle s={\texttt {bear}}}$, and ${\displaystyle t={\texttt {hug}}}$, then ${\displaystyle st={\texttt {bearhug}}}$ and ${\displaystyle ts={\texttt {hugbear}}}$.

String concatenation is an associative, but non-commutative operation. The empty string ${\displaystyle \varepsilon }$ serves as the identity element; for any string ${\displaystyle s}$, ${\displaystyle \varepsilon s=s\varepsilon =s}$. Therefore, the set ${\displaystyle \Sigma ^{*}}$ and the concatenation operation form a monoid, the free monoid generated by ${\displaystyle \Sigma }$. In addition, the length function defines a monoid homomorphism from ${\displaystyle \Sigma ^{*}}$ to the non-negative integers (that is, a function ${\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}}$, such that ${\displaystyle L(st)=L(s)+L(t)\quad \forall s,t\in \Sigma ^{*}}$).

A string ${\displaystyle s}$ is said to be a substring or factor of ${\displaystyle t}$ if there exist (possibly empty) strings ${\displaystyle u}$ and ${\displaystyle v}$ such that ${\displaystyle t=usv}$. The relation "is a substring of" defines a partial order on ${\displaystyle \Sigma ^{*}}$, the least element of which is the empty string.

Prefixes and suffixes

A string ${\displaystyle s}$ is said to be a prefix of ${\displaystyle t}$ if there exists a string ${\displaystyle u}$ such that ${\displaystyle t=su}$. If ${\displaystyle u}$ is nonempty, ${\displaystyle s}$ is said to be a proper prefix of ${\displaystyle t}$. Symmetrically, a string ${\displaystyle s}$ is said to be a suffix of ${\displaystyle t}$ if there exists a string ${\displaystyle u}$ such that ${\displaystyle t=us}$. If ${\displaystyle u}$ is nonempty, ${\displaystyle s}$ is said to be a proper suffix of ${\displaystyle t}$. Suffixes and prefixes are substrings of ${\displaystyle t}$. Both the relations "is a prefix of" and "is a suffix of" are prefix orders.

Reversal

The reverse of a string is a string with the same symbols but in reverse order. For example, if ${\displaystyle s={\texttt {abc}}}$ (where ${\displaystyle {\texttt {a}}}$, ${\displaystyle {\texttt {b}}}$, and ${\displaystyle {\texttt {c}}}$ are symbols of the alphabet), then the reverse of ${\displaystyle s}$ is ${\displaystyle {\texttt {cba}}}$. A string that is the reverse of itself (e.g., ${\displaystyle s={\texttt {madam}}}$) is called a palindrome, which also includes the empty string and all strings of length ${\displaystyle 1}$.

Rotations

A string ${\displaystyle s=uv}$ is said to be a rotation of ${\displaystyle t}$ if ${\displaystyle t=vu}$. For example, if ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ the string ${\displaystyle {\texttt {0011001}}}$ is a rotation of ${\displaystyle {\texttt {0100110}}}$, where ${\displaystyle u={\texttt {00110}}}$ and ${\displaystyle v={\texttt {01}}}$. As another example, the string ${\displaystyle {\texttt {abc}}}$ has three different rotations, viz. ${\displaystyle {\texttt {abc}}}$ itself (with ${\displaystyle u={\texttt {abc}}}$, ${\displaystyle v=\varepsilon }$), ${\displaystyle {\texttt {bca}}}$ (with ${\displaystyle u={\texttt {bc}},v={\texttt {a}}}$), and ${\displaystyle {\texttt {cab}}}$ (with ${\displaystyle u={\texttt {c}},v={\texttt {ab}}}$).

Lexicographical ordering

It is often useful to define an ordering on a set of strings. If the alphabet ${\displaystyle \Sigma }$ has a total order (cf. alphabetical order) one can define a total order on ${\displaystyle \Sigma ^{*}}$ called lexicographical order. The lexicographical order is total if the alphabetical order is, but is not well-founded for any nontrivial alphabet, even if the alphabetical order is. For example, if ${\displaystyle \Sigma =\{{\texttt {0}},{\texttt {1}}\}}$ and ${\displaystyle {\texttt {0}}<{\texttt {1}}}$, then the lexicographical order on ${\displaystyle \Sigma ^{*}}$ includes the relationships ${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {00}}<{\texttt {000}}<...<{\texttt {0001}}<...<{\texttt {001}}<...<{\texttt {01}}<{\texttt {010}}<...<{\texttt {011}}<{\texttt {0110}}<...<{\texttt {01111}}<...<{\texttt {1}}<{\texttt {10}}<{\texttt {100}}<...<{\texttt {101}}<...<{\texttt {111}}<...<{\texttt {1111}}<...<{\texttt {11111}}...}$ With respect to this ordering, e.g. the infinite set ${\displaystyle \{{\texttt {1}},{\texttt {01}},{\texttt {001}},{\texttt {0001}},{\texttt {00001}},{\texttt {000001}},...\}}$ has no minimal element.

See Shortlex for an alternative string ordering that preserves well-foundedness. For the example alphabet, the shortlex order is ${\displaystyle \varepsilon <{\texttt {0}}<{\texttt {1}}<{\texttt {00}}<{\texttt {01}}<{\texttt {10}}<{\texttt {11}}<{\texttt {000}}<{\texttt {001}}<{\texttt {010}}<{\texttt {011}}<{\texttt {100}}<{\texttt {101}}<{\texttt {0110}}<{\texttt {111}}<{\texttt {0000}}<{\texttt {0001}}<{\texttt {0010}}<{\texttt {0011}}<...<{\texttt {1111}}<{\texttt {00000}}<{\texttt {00001}}...}$

String operations

A number of additional operations on strings commonly occur in the formal theory. These are given in the article on string operations.

Topology

Strings admit the following interpretation as nodes on a graph, where ${\displaystyle k}$ is the number of symbols in ${\displaystyle \Sigma }$:

• Fixed-length strings of length ${\displaystyle n}$ can be viewed as the integer locations in an ${\displaystyle n}$-dimensional hypercube with sides of length ${\displaystyle k-1}$.
• Variable-length strings (of finite length) can be viewed as nodes on a perfect ${\displaystyle k}$-ary tree.
• Infinite strings (otherwise not considered here) can be viewed as infinite paths on a ${\displaystyle k}$-node complete graph.

The natural topology on the set of fixed-length strings or variable-length strings is the discrete topology, but the natural topology on the set of infinite strings is the limit topology, viewing the set of infinite strings as the inverse limit of the sets of finite strings. This is the construction used for the p-adic numbers and some constructions of the Cantor set, and yields the same topology.

Isomorphisms between string representations of topologies can be found by normalizing according to the lexicographically minimal string rotation.