# String (computer science)

## Information about String (computer science)

In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. These symbols are chosen from a predetermined set.

In programming, when stored in memory each symbol is represented using a numeric value. A variable declared to have a string datatype usually causes storage to be allocated in memory that is capable of holding some predetermined number of symbols. When it appears in source code a string is known as a string literal and has a representation that denotes it as such. Sometimes the term binary string is used to refer to an arbitrary sequence of bits.

## Formal theory

Let Σ be an alphabet, a non-empty finite set. Elements of Σ are called symbols or characters. A string (or word) over Σ is any finite sequence of characters from Σ. For example, if Σ = {0, 1}, then 0101 is a string over Σ.

The length of a string is the number of characters in the string (the length of the sequence) and can be any non-negative integer. The empty string is the unique string over Σ of length 0, and is denoted ε or λ.

The set of all strings over Σ of length n is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. Note that Σ0 = {ε} for any alphabet Σ.

The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn, . For example, if Σ = {0, 1}, Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}. Although Σ* itself is countably infinite, all elements of Σ* have finite length.

A set of strings over Σ (i.e. any subset of Σ*) is called a formal language over Σ. For example, if Σ = {0, 1}, the set of strings with an even number of zeros ({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …}) is a formal language over Σ.

### Concatenation and substrings

Concatenation is an important binary operation on Σ*. For any two strings s and t in Σ*, their concatenation is defined as the sequence of characters in s followed by the sequence of characters in t, and is denoted st. For example, if Σ = {a, b, …, z}, s = bear, and t = hug, then st = bearhug and ts = hugbear.

String concatenation is an associative, but non-commutative operation. The empty string serves as the identity element; for any string s, εs = sε = s. Therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers.

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

### Lexicographical ordering

It is often necessary to define an ordering on the set of strings. If the alphabet Σ has a total order (cf. alphabetical order) one can define a total order on Σ* called lexicographical order. Note that since Σ is finite, it is always possible to define a well ordering on Σ and thus on Σ*. For example, if Σ = {0, 1} and 0 < 1, then the lexicographical ordering of Σ* is ε < 0 < 00 < 000 < … < 011 < 0110 < … < 01111 < … < 1 < 10 < 100 < … < 101 < … < 111 ?

### String operations

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

## String datatypes

A string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every programming language. In some languages they are available as primitive types and in others as composite types. The syntax of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a literal or string literal.

### String length

Although formal strings can have an arbitrary (but 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 and which use the same amount of memory whether this maximum is reached or not, and variable length strings whose length is not arbitrarily fixed and which use varying amounts of memory depending on their actual size. Most strings in modern programming languages are variable length strings. Despite the name, even variable length strings are limited in length; although, generally, the limit depends only on the amount of memory available..

### Character encoding

Historically, string datatypes allocated one byte per character, and although the exact character set varied by region, character encodings were similar enough that programmers could generally get away with ignoring this — groups of character sets used by the same system in different regions either had a character in the same place, or did not have it at all. These character sets were typically based on ASCII or EBCDIC.

Logographic languages such as Chinese, Japanese, and Korean (known collectively as CJK) need far more than 256 characters (the limit of a one-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 only represent 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. Another issue is that if the beginning of a string is deleted, important instructions for the decoder or information on position in a multibyte sequence may be lost. Another is that if strings are joined together (especially after having their ends truncated by code not aware of the encoding), the first string may not leave the encoder in a state suitable for dealing with the second string.

Unicode has complicated the picture somewhat. Most languages have a datatype for Unicode strings (usually UTF-16 as it was usually added before Unicode supplemental planes were introduced). Converting between Unicode and local encodings requires an understanding of the local encoding, which may be problematic for existing systems where strings of various encodings are being transmitted together with no real marking as to what encoding they are in.

### Implementations

Some languages like C++ implement strings as templates that can be used with any primitive type, but this is the exception, not the rule.

If an object-oriented language represents strings as objects, they are called mutable if the value can change at runtime and immutable if the value is frozen after creation. For example, Ruby has mutable strings, while Python's strings are immutable.

Other languages, most notably Prolog and Erlang, avoid implementing a string datatype, instead adopting the convention of representing strings as lists of character codes.

### 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.

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 characters can take anywhere from one to four bytes. In these cases, the logical length of the string differs from the logical length of the array.

The length of a string can be stored implicitly by using a special terminating character; often this is the null character having value zero, a convention used and perpetuated by the popular C programming language[1]. Hence, this representation is commonly referred to as C string. The length of a string can also be stored explicitly, for example by prefixing the string with byte value — a convention used in Pascal; consequently some people call it a P-string.

In terminated strings, the terminating code is not an allowable character in any string.

Here is an example of a null-terminated string stored in a 10-byte buffer, along with its ASCII representation:

 F R A N K NUL k e f w 46 52 41 4E 4B 00 6B 66 66 77

The length of a string in the above example is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of another string or just garbage. (Strings of this form are sometimes called ASCIZ strings, after the original assembly language directive used to declare them.)

Here is the equivalent (old style) Pascal string stored in a 10-byte buffer, along with its ASCII representation:

 length F R A N K k e f w 05 46 52 41 4E 4B 6B 66 66 77

While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.

## Vectors

While character strings are very common uses of strings, a string in computer science may refer generically to any vector of homogenously typed data. A string of bits or bytes, for example, may be used to represent data retrieved from a communications medium. This data may or may not be represented by a string-specific datatype, depending on the needs of the application, the desire of the programmer, and the capabilities of the programming language being used.

## String processing algorithms

There are many algorithms for processing strings, each with various trade-offs. Some categories of algorithms include
Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines.

## Character string oriented languages and utilities

Character strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include the following languages: Many UNIX utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings.

Some Application Programming Interfaces like Multimedia Control Interface, embedded SQL or printf use strings to hold commands that will be interpreted.

Recent scripting programming languages, including Perl, Python, Ruby, and Tcl employ regular expressions to facilitate text operations.

## Character string functions

String functions are used to manipulate a string or change or edit the contents of a string. They also are used to query information about a string. They are usually used within the context of a computer programming language.

The most basic example of a string function is the length(string) function. This function returns the length of a string (not counting the null terminator or any other of the string's internal structural information) and does not change the string.

eg. length("hello world") would return 11.

There are many string functions which exist in other languages with similar or exactly the same syntax or parameters. For example in many languages the length function is usually represented as len(string). Even though string functions are very useful to a computer programmer, a computer programmer using these functions should be mindful that a string function in one language could in another language behave differently or have a similar or completely different function name, parameters, syntax and outcomes.

## Notes

1. ^ Bryant, Randal E. & O'Hallaron David (2003), Computer Systems: A Programmer's Perspective (2003 ed.), Upper Saddle River, NJ: Pearson Education, pp. 40, ISBN 0-13-034074-X , <[1]

Computer programming (often shortened to programming or coding) is the process of writing, testing, and maintaining the source code of computer programs. The source code is written in a programming language.

Mathematics (colloquially, maths or math) is the body of knowledge centered on such concepts as quantity, structure, space, and change, and also the academic discipline that studies them. Benjamin Peirce called it "the science that draws necessary conclusions".
sequence is an ordered list of objects (or events). Like a set, it contains members (also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence.
Symbols are objects, characters, or other concrete representations of ideas, concepts, or other abstractions. For example, in the United States, Canada and Great Britain, a red octagon is a symbol for the traffic sign meaning "STOP".
SET may stand for:
• Sanlih Entertainment Television, a television channel in Taiwan
• Secure electronic transaction, a protocol used for credit card processing,

variable (IPA pronunciation: [ˈvæɹiəbl]) (sometimes called a pronumeral) is a symbolic representation denoting a quantity or expression.
In programming languages a data type defines a set of values and the allowable operations on those values[1]. For example, in the Java programming language, the "int" type represents the set of 32-bit integers ranging in value from -2,147,483,648 to 2,147,483,647, and
source code (commonly just source or code) is any sequence of statements and/or declarations written in some human-readable computer programming language.
A string literal is the representation of a string value within the source code of a computer program. There exist numerous alternate notations for specifying string literals, and the exact notation depends on the individual programming language in question.
In computer science, an alphabet is a finite set of characters or digits. The most common alphabet is {0,1}, the binary alphabet. A finite string is a finite sequence of characters from an alphabet; for instance a binary string is a string drawn from the alphabet {0,1}.
empty set is the unique set which contains no elements. In axiomatic set theory it is postulated to exist by the axiom of empty set. The empty set is also sometimes called the null set
In mathematics, a set is called finite if there is a bijection between the set and some set of the form where n is a natural number. (The value n = 0 is allowed; that is, the empty set is finite.) An infinite set is a set which is not finite.
SET may stand for:
• Sanlih Entertainment Television, a television channel in Taiwan
• Secure electronic transaction, a protocol used for credit card processing,

sequence is an ordered list of objects (or events). Like a set, it contains members (also called elements or terms), and the number of terms (possibly infinite) is called the length of the sequence.
Length is the long dimension of any object. The length of a thing is the distance between its ends, its linear extent as measured from end to end. This may be distinguished from height, which is vertical extent, and width or breadth
In mathematics, a natural number can mean either an element of the set (i.e the positive integers or the counting numbers) or an element of the set (i.e. the non-negative integers).
In computer science, the empty string is the unique string of no characters over some alphabet Σ, and is denoted ε or λ. The length of this empty string is 0.
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*.
countable set is a set with the same cardinality (i.e., number of elements) as some subset of the set of natural numbers. The term was originated by Georg Cantor; it stems from the fact that the natural numbers are often called counting numbers.
subset of a set B if A is "contained" inside B. Notice that A and B may coincide. The relationship of one set being a subset of another is called inclusion or containment.

Concatenation is a standard operation in computer programming languages (a subset of formal language theory). It is the operation of joining two character strings end to end. For example, the strings "foo" and "bar" may be concatenated to give "foobar".
In mathematics, a binary operation is a calculation involving two input quantities, in other words, an operation whose arity is two. Binary operations can be accomplished using either a binary function or binary operator.
associativity is a property that a binary operation can have. It means that, within an expression containing two or more of the same associative operators in a row, the order of operations does not matter as long as the sequence of the operands is not changed.