HOME

TheInfoList




In
computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, generating algorithms, Profilin ...
, a string is traditionally a
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
of
characters Character(s) may refer to: Arts, entertainment, and media Literature * Character (novel), ''Character'' (novel), a 1936 Dutch novel by Ferdinand Bordewijk * Characters (Theophrastus), ''Characters'' (Theophrastus), a classical Greek set of char ...
, either as a literal constant or as some kind of variable. The latter may allow its elements to be mutated and the length changed, or it may be fixed (after creation). A string is generally considered as a
data type In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...
and is often implemented as an
array data structure ARRAY, also known as ARRAY Now, is an independent distribution company launched by film maker and former publicist Ava DuVernay Ava Marie DuVernay (; born August 24, 1972) is an American filmmaker. She won the directing award in the U.S. dram ...
of
byte The byte is a unit of digital information that most commonly consists of eight bit The bit is a basic unit of information in computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It ...
s (or
word In linguistics Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed language, sign language) and writing. Most lang ...
s) that stores a sequence of elements, typically characters, using some
character encoding Character encoding is the process of assigning numbers to graphical Graphics (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country ...
. ''String'' may also denote more general
arrays ARRAY, also known as ARRAY Now, is an independent distribution company launched by film maker and former publicist Ava DuVernay Ava Marie DuVernay (; born August 24, 1972) is an American filmmaker. She won the directing award in the U.S. drama ...
or other sequence (or
list A ''list'' is any set of items. List or lists may also refer to: People * List (surname)List or Liste is a European surname. Notable people with the surname include: List * Friedrich List (1789–1846), German economist * Garrett List (194 ...
) data types and structures. Depending on the programming language and precise data type used, a variable declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ
dynamic allocation In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , ...
to allow it to hold a variable number of elements. When a string appears literally in
source code In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and ...

source code
, it is known as a
string literal A string literal or anonymous string is a type of literal Literal may refer to: * Interpretation of legal concepts: ** Strict constructionism ** The plain meaning rule (a.k.a. "literal rule") * Literal (mathematical logic), certain logical r ...
or an anonymous string. In
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science), alphabet and are well-formedness, well-formed a ...
s, which are used in
mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal sys ...
and
theoretical computer science Theoretical computer science (TCS) is a subset of general computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for the ...

theoretical computer science
, a string is a finite sequence of
symbol A symbol is a mark, sign, or word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semantic, objective or pragmatics, practical meaning (linguistics), m ...
s that are chosen from a set called an
alphabet An alphabet is a standardized set of basic written symbols A symbol is a mark, sign, or word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semanti ...
.


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 A programming language is a formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science) ...

programming language
. In some languages they are available as
primitive type In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algorit ...
s and in others as
composite type In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of comp ...
s. The
syntax In linguistics Linguistics is the scientific study of language, meaning that it is a comprehensive, systematic, objective, and precise study of language. Linguistics encompasses the analysis of every aspect of language, as well as 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 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 In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of co ...
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 Memory management is a form of resource management In organizational studies Organizational studies is "the examination of how individuals construct organizational structures, processes, and practices and how these, in turn, shape social relat ...
). Most strings in modern
programming languages A programming language is a formal language comprising a set of Formal language#Words over an alphabet, strings that produce various kinds of Machine code, machine code output. Programming languages are one kind of computer language, and are us ...
are variable-length strings. Of course, even variable-length strings are limited in length – by the size of available
computer memory In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and soft ...
. 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 ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding Character encoding is the process of assigning numbers to graphical Graphics (from Greek Greek may refer to: Greece Anything of, ...
or
EBCDIC Extended Binary Coded Decimal Interchange Code (EBCDIC; ) is an eight-bit character encoding used mainly on IBM mainframe and IBM midrange computer operating systems. It descended from the code used with punched cards and the corresponding six-b ...
. If text in one encoding was displayed on a system using a different encoding, text was often
mangled
mangled
, though often somewhat readable and some computer users learned to read the mangled text.
Logograph In a written language A written language is the representation of a spoken or gestural language by means of a writing system. Written language is an invention in that it must be taught to children, who will pick up spoken language or sign ...
ic languages such as
Chinese Chinese can refer to: * Something related to China China, officially the People's Republic of China (PRC), is a country in East Asia. It is the List of countries and dependencies by population, world's most populous country, with a populat ...
,
Japanese Japanese may refer to: * Something from or related to Japan Japan ( ja, 日本, or , and formally ) is an island country An island country or an island nation is a country A country is a distinct territory, territorial body or ...

Japanese
, and
Korean Korean may refer to: People and culture * Koreans, ethnic group originating in the Korean Peninsula * Korean cuisine * Korean culture * Korean language **Korean alphabet, known as Hangul or Chosŏn'gŭl **Korean dialects and the Jeju language **S ...
(known collectively as
CJK In internationalization, CJK characters is a collective term for the Chinese, Japanese, and Korean Korean may refer to: People and culture * Koreans, an ethnic group originating in the Korean Peninsula * Korean cuisine * Korean culture * Kor ...
) 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 An ideogram or ideograph (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeast Europe. Its population is approxima ...
. 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 ISO/IEC 2022 ''Information technology—Character code structure and extension techniques'', is an International Organization for Standardization, ISO standard (equivalent to the Ecma International, ECMA standard ECMA-35, the ANSI standard ANSI ...
and
Shift-JIS Shift JIS (Shift Japanese Industrial Standards, also SJIS, MIME Multipurpose Internet Mail Extensions (MIME) is an Internet standard that extends the format of email messages to support text in character sets other than ASCII, as well as attac ...
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 Unicode, formally the Unicode Standard, is an information technology Technical standard, standard for the consistent character encoding, encoding, representation, and handling of Character (computing), text expressed in most of the world's wri ...

Unicode
has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format
UTF-8 UTF-8 is a variable-width character encoding Character encoding is the process of assigning numbers to Graphics, graphical character (computing), characters, especially the written characters of Language, human language, allowing them to be ...
is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and
UTF-32 UTF-32 (32-bit The bit is a basic unit of information in computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and deve ...
require the programmer to know that the fixed-size code units are different than 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++ and
Ruby A ruby is a pink-ish red to blood-red colored gemstone A gemstone (also called a fine gem, jewel, precious stone, or semi-precious stone) is a piece of mineral In geology and mineralogy, a mineral or mineral species is, broadly spea ...
, 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 Java ( id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 147.7 million people, Java is the world's List of ...
and
Python PYTHON was a Cold War contingency plan of the Government of the United Kingdom, British Government for the continuity of government in the event of Nuclear warfare, nuclear war. Background Following the report of the Strath Committee in 1955, the ...
, 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 also provide another type that is mutable, such as Java and
.NET The domain name net is a generic top-level domain (gTLD) used in the Domain Name System of the Internet. The name is derived from the word ''network'', indicating it was originally intended for organizations involved in networking technologies, ...
, the thread-safe Java , and the
Cocoa CoCoA (Computations in Commutative Algebra) is a free computer algebra system developed by the University of Genova, Italy, used to compute with numbers and polynomials. The CoCoA Library (CoCoALib) is available under GNU General Public License. ...
NSMutableString). Strings are typically implemented as
arrays ARRAY, also known as ARRAY Now, is an independent distribution company launched by film maker and former publicist Ava DuVernay Ava Marie DuVernay (; born August 24, 1972) is an American filmmaker. She won the directing award in the U.S. drama ...
of bytes, characters, or code units, in order 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 list In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...

linked list
s instead. Some languages, such as
Prolog Prolog is a logic programming Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some ...

Prolog
and Erlang, avoid implementing a dedicated string datatype at all, 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 ISO/IEC 8859 is a joint ISO The International Organization for Standardization (ISO ) is an international standard An international standard is a technical standard A technical standard is an established norm (social), norm or requirement for ...
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
array ARRAY, also known as ARRAY Now, is an independent distribution company launched by film maker and former publicist Ava DuVernay Ava Marie DuVernay (; born August 24, 1972) is an American filmmaker. She won the directing award in the U.S. dram ...
s with the entries storing the
character code In computing, Computer data storage, data storage, and data transmission, character encoding is used to represent a repertoire of character (computing), characters by some kind of code, encoding system that assigns a number to each character for ...
s 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 UTF-32 (32-bit The bit is a basic unit of information in computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and deve ...
avoids the first part of the problem.


Null-terminated

The length of a string can be stored implicitly by using a special terminating character; often this is the
null character The null character (also null terminator) is a control character In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithm of ...
(NUL), which has all bits zero, a convention used and perpetuated by the popular
C programming language C (, as in the letter ''c'') is a general-purpose, procedural computer programming language A programming language is a formal language comprising a Instruction set architecture, set of instructions that produce various kinds of Input/outp ...
. Hence, this representation is commonly referred to as a C string. This representation of an ''n''-character string takes ''n'' + 1 space (1 for the terminator), and is thus an
implicit data structureIn computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low Overhead (computing), overhead. They ar ...
. In terminated strings, the terminating code is not an allowable character in any string. Strings with ''length'' field do not have this limitation and can also store arbitrary
binary data Binary data is data Data (; ) are individual facts, statistics, or items of information, often numeric. In a more technical sense, data are a set of values of qualitative property, qualitative or quantity, quantitative variable (research), v ...
. An example of a ''null-terminated string'' stored in a 10-byte
buffer Buffer may refer to: Science * Buffer gas, an inert or nonflammable gas * Buffer solution, a solution used to prevent changes in pH * Buffering agent, the weak acid or base in a buffer solution * Lysis buffer, in cell biology * Metal ion buffer * M ...
, along with its
ASCII ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding Character encoding is the process of assigning numbers to graphical Graphics (from Greek Greek may refer to: Greece Anything of, ...
(or more modern
UTF-8 UTF-8 is a variable-width character encoding Character encoding is the process of assigning numbers to Graphics, graphical character (computing), characters, especially the written characters of Language, human language, allowing them to be ...
) representation as 8-bit
hexadecimal number In mathematics and computing, the hexadecimal (also base 16 or hex) numeral system is a Numeral system#Positional systems in detail, positional numeral system that represents numbers using a radix (base) of 16. Unlike the decimal, common way of ...
s is: The length of the string in the above example, "FRANK", 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 other data or just garbage. (Strings of this form are sometimes called ''ASCIZ strings'', after the original
assembly language In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, gene ...
directive used to declare them.)


Byte- and bit-terminated

Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character. $ was used by many assembler systems, : used by
CDC CDC may refer to: Organizations Government * Centers for Disease Control and Prevention The United States The United States of America (USA), commonly known as the United States (U.S. or US), or America, is a country Contiguous Unite ...
systems (this character had a value of zero), and the
ZX80 The Sinclair ZX80 is a home computer Home computers were a class of s that entered the market in 1977 and became common during the 1980s. They were marketed to consumers as affordable and accessible computers that, for the first time, were ...

ZX80
used " since this was the string delimiter in its BASIC language. Somewhat similar, "data processing" machines like the
IBM 1401 The IBM 1401 is a variable-wordlength decimal computer Decimal computers are computers which can represent numbers and addresses in decimal The decimal numeral system A numeral system (or system of numeration) is a writing system ...
used a special word mark bit to delimit strings at the left, where the operation would start at the right. This bit had to be clear in all other parts of the string. This meant that, while the IBM 1401 had a seven-bit word, almost no-one ever thought to use this as a feature, and override the assignment of the seventh bit to (for example) handle ASCII codes. Early microcomputer software relied upon the fact that ASCII codes do not use the high-order bit, and set it to indicate the end of a string. It must be reset to 0 prior to output.


Length-prefixed

The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value. This convention is used in many
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, French ...
dialects; as a consequence, some people call such a string a Pascal string or P-string. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit
words In linguistics Linguistics is the scientific study of language A language is a structured system of communication used by humans, including speech (spoken language), gestures (Signed language, sign language) and writing. Most lang ...
to store the string length. When the ''length'' field covers the
address space In computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and development of both computer hardware , hardware and softwa ...
, strings are limited only by the available memory. If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an
implicit data structureIn computer science, an implicit data structure or space-efficient data structure is a data structure that stores very little information other than the main or required data: a data structure that requires low Overhead (computing), overhead. They ar ...
, taking ''n'' + ''k'' space, where ''k'' is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.). If the length is not bounded, encoding a length ''n'' takes log(''n'') space (see fixed-length code), so length-prefixed strings are a succinct data structure, encoding a string of length ''n'' in log(''n'') + ''n'' space. In the latter case, the length-prefix field itself doesn't have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased. Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:


Strings as records

Many languages, including object-oriented ones, implement strings as records with an internal structure like: class string ; However, since the implementation is usually hidden, the string must be accessed and modified through member functions. text is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also
string (C++) The C++ programming language has support for String (computer science), string handling, mostly implemented in its C++ Standard Library, standard library. The language standard specifies several string types, some inherited from C (programming langu ...
.


Other representations

Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by
C string The C programming language has a set of functions implementing operations on strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other ...
library functions: Strings using a length code are limited to the maximum value of the length code. Both of these limitations can be overcome by clever programming. It is possible to create data structures and functions that manipulate them that do not have the problems associated with character termination and can in principle overcome length code bounds. It is also possible to optimize the string represented using techniques from
run length encoding Run-length encoding (RLE) is a form of lossless data compression in which ''runs'' of data (sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original ru ...
(replacing repeated characters by the character value and a length) and Hamming encoding. While these representations are common, others are possible. Using
rope A rope is a group of yarns, Plying, plies, fibers or strands that are twisted or braided together into a larger and stronger form. Ropes have tensile strength and so can be used for dragging and lifting. Rope is thicker and stronger than simil ...
s makes certain string operations, such as insertions, deletions, and concatenations more efficient. The core data structure in a
text editor A text editor is a type of computer program In imperative programming, a computer program is a sequence of instructions in a programming language that a computer can execute or interpret. In declarative programming, a ''computer program'' is ...

text editor
is the one that manages the string (sequence of characters) that represents the current state of the file being edited. While that state could be stored in a single long consecutive array of characters, a typical text editor instead uses an alternative representation as its sequence data structure—a
gap buffer A gap buffer in computer science is a dynamic array that allows efficient insertion and deletion operations clustered near the same location. Gap buffers are especially common in text editors, where most changes to the text occur at or near the cur ...
, a
linked list In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , ...

linked list
of lines, a piece table, or a
rope A rope is a group of yarns, Plying, plies, fibers or strands that are twisted or braided together into a larger and stronger form. Ropes have tensile strength and so can be used for dragging and lifting. Rope is thicker and stronger than simil ...
—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.


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 In information security #REDIRECT Information security Information security, sometimes shortened to infosec, is the practice of protecting information by mitigating information risks. It is part of Risk management information systems, information ...
problems if the terminating character is not present, caused by a coding error or an
attacker In some team sport A team is a [group (disambiguation), group of individuals (human or non-human) working together to achieve their goal. As defined by Professor Leigh Thompson (academic), Leigh Thompson of the Kellogg School of Management, ...
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 Code injection is the exploitation of a computer bug A software bug is an error, flaw or fault in a computer program A computer program is a collection of instructions that can be executed by a computer to perform a specific task. A ...
attacks.


Literal strings

Sometimes, strings need to be embedded inside a text file that is both human-readable and intended for consumption by a machine. This is needed in, for example, source code of programming languages, or in configuration files. In this case, the NUL character doesn't work well as a terminator since it is normally invisible (non-printable) and is difficult to input via a keyboard. Storing the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone. Two common representations are: * Surrounded by
quotation mark Quotation marks, also known as quotes, quote marks, speech marks, inverted commas, or talking marks, are punctuation Punctuation (or sometimes interpunction) is the use of spacing, conventional signs (called punctuation marks), and cer ...
s (ASCII 0x22 double quote or ASCII 0x27 single quote), used by most programming languages. To be able to include special characters such as the quotation mark itself, newline characters, or non-printable characters,
escape sequence In computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of Algo ...
s are often available, usually prefixed with the
backslash The backslash is a typographical mark used mainly in computing Computing is any goal-oriented activity requiring, benefiting from, or creating computing machinery. It includes the study and experimentation of algorithmic processes and develop ...
character (ASCII 0x5C). * Terminated by a
newline Newline (frequently called line ending, end of line (EOL), next line (NEL) or line break) is a control character or sequence of control characters in a character encoding specification (e.g., ASCII, EBCDIC) that is used to signify the end of a ...

newline
sequence, for example in Windows
INI file An INI file is a configuration file for computer software that consists of a text-based content with a structure and syntax comprising key-value pairs for properties, and sections that organize the properties. The name of these configuration files ...
s.


Non-text strings

While character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data. A
bit string A bit array (also known as bit map, bit set, bit string, or bit vector) is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in ...
or
byte string In computer programming Computer programming is the process of designing and building an executable computer program to accomplish a specific computing result or to perform a particular task. Programming involves tasks such as analysis, ge ...
, for example, may be used to represent non-textual
binary data Binary data is data Data (; ) are individual facts, statistics, or items of information, often numeric. In a more technical sense, data are a set of values of qualitative property, qualitative or quantity, quantitative variable (research), v ...
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. If the programming language's string implementation is not
8-bit clean The phrase ''8-bit clean'' describes a computer system A computer is a machine that can be programmed to carry out Sequence, sequences of arithmetic or logical operations automatically. Modern computers can perform generic sets of operations ...
, data corruption may ensue. C programmers draw a sharp distinction between a "string", aka a "string of characters", which by definition is always null terminated, vs. a "byte string" or "pseudo string" which may be stored in the same array but is often not null terminated. Using
C string handling The C programming language has a set of functions implementing operations on strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other ...
functions on such a "byte string" often seems to work, but later leads to security problems.


String processing algorithms

There are many
algorithm In and , an algorithm () is a finite sequence of , computer-implementable instructions, typically to solve a class of problems or to perform a computation. Algorithms are always and are used as specifications for performing s, , , and other ...

algorithm
s for processing strings, each with various trade-offs. Competing algorithms can be analyzed with respect to run time, storage requirements, and so forth. Some categories of algorithms include: * String searching algorithms for finding a given substring or pattern * String manipulation algorithms *
Sorting algorithm In computer science, a sorting algorithm is an algorithm that puts elements of a List (computing), list into an Total order, order. The most frequently used orders are numerical order and lexicographical order, and either ascending or descending. E ...
s *
Regular expression A regular expression (shortened as regex or regexp; also referred to as rational expression) is a sequence of Character (computing), characters that specifies a ''search pattern matching, pattern''. Usually such patterns are used by string-se ...
algorithms *
Parsing Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other obj ...

Parsing
a string *
Sequence mining In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite-state machines. The name ''stringology'' was coined in 1984 by computer scientist Zvi Galil for the issue of algorithms and data structures used for string processing.


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: * AWK (programming language), awk * Icon (programming language), Icon * MUMPS * Perl * Rexx *
Ruby A ruby is a pink-ish red to blood-red colored gemstone A gemstone (also called a fine gem, jewel, precious stone, or semi-precious stone) is a piece of mineral In geology and mineralogy, a mineral or mineral species is, broadly spea ...
* sed * SNOBOL * Tcl * TTM (programming language), TTM 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 interface, APIs like Multimedia Control Interface, embedded SQL or printf use strings to hold commands that will be interpreted. Recent scripting programming languages, including Perl,
Python PYTHON was a Cold War contingency plan of the Government of the United Kingdom, British Government for the continuity of government in the event of Nuclear warfare, nuclear war. Background Following the report of the Strath Committee in 1955, the ...
, Ruby, and Tcl employ regular expressions to facilitate text operations. Perl is particularly noted for its regular expression use, and many other languages and applications implement Perl Compatible Regular Expressions, Perl compatible regular expressions. Some languages such as Perl and Ruby support string interpolation, which permits arbitrary expressions to be evaluated and included in string literals.


Character string functions

String functions are used to create strings or change the contents of a mutable string. They also are used to query information about a string. The set of functions and their names varies depending on the programming language, computer programming language. The most basic example of a string function is the string length function – the function that returns the length of a string (not counting any terminator characters or any of the string's internal structural information) and does not modify the string. This function is often named comparison of programming languages (string functions)#length , length or len. For example, length("hello world") would return 11. Another common function is concatenation, where a new string is created by appending two strings, often this is the + addition operator. Some microprocessor's instruction set architectures contain direct support for string operations, such as block copy (e.g. In intel x86m REPNZ MOVSB).


Formal theory

Let Σ be a finite set of symbols (alternatively called characters), called the Alphabet (formal languages), alphabet. No assumption is made about the nature of the symbols. A string (or word) over Σ is any finite
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
of symbols from Σ. For example, if Σ = , then ''01011'' is a string over Σ. The ''length'' of a string ''s'' is the number of symbols in ''s'' (the length of the sequence) and can be any non-negative integer; it is often denoted as , ''s'', . The ''empty string'' is the unique string over Σ of length 0, and is denoted ''ε'' or ''λ''. Here: sect.1.1, p.1 The set of all strings over Σ of length ''n'' is denoted Σ''n''. For example, if Σ = , then Σ2 = . Note that Σ0 = for any alphabet Σ. The set of all strings over Σ of any length is the Kleene star, Kleene closure of Σ and is denoted Σ*. In terms of Σ''n'', :\Sigma^ = \bigcup_ \Sigma^ For example, if Σ = , then Σ* = . Although the set Σ* itself is countably infinite, each element of Σ* is a string of finite length. A set of strings over Σ (i.e. any subset of Σ*) is called a ''
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of string (computer science), words whose symbol (formal), letters are taken from an alphabet (computer science), alphabet and are well-formedness, well-formed a ...
'' over Σ. For example, if Σ = , the set of strings with an even number of zeros, , 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 symbols in ''s'' followed by the sequence of characters in ''t'', and is denoted ''st''. For example, if Σ = , ''s'' = , and ''t'' = , then ''st'' =  and ''ts'' = . 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 (that is, a function L: \Sigma^ \mapsto \mathbb \cup \, such that L(st)=L(s)+L(t)\quad \forall s,t\in\Sigma^*). 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 binary relation, relation "is a substring of" defines a partial order on Σ*, the least element of which is the empty string.


Prefixes and suffixes

A string ''s'' is said to be a Substring#Prefix, prefix of ''t'' if there exists a string ''u'' such that ''t'' = ''su''. If ''u'' is nonempty, ''s'' is said to be a ''proper'' prefix of ''t''. Symmetrically, a string ''s'' is said to be a Substring#Suffix, suffix of ''t'' if there exists a string ''u'' such that ''t'' = ''us''. If ''u'' is nonempty, ''s'' is said to be a ''proper'' suffix of ''t''. Suffixes and prefixes are substrings of ''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 ''s'' = abc (where a, b, and c are symbols of the alphabet), then the reverse of ''s'' is cba. A string that is the reverse of itself (e.g., ''s'' = madam) is called a palindrome#Computation theory, palindrome, which also includes the empty string and all strings of length 1.


Rotations

A string ''s'' = ''uv'' is said to be a rotation of ''t'' if ''t'' = ''vu''. For example, if Σ = the string 0011001 is a rotation of 0100110, where ''u'' = 00110 and ''v'' = 01. As another example, the string abc has three different rotations, viz. abc itself (with ''u''=abc, ''v''=ε), bca (with ''u''=bc, ''v''=a), and cab (with ''u''=c, ''v''=ab).


Lexicographical ordering

It is often useful to define an order theory, ordering on a set of strings. If the alphabet Σ has a total order (cf. alphabetical order) one can define a total order on Σ* called lexicographical order. For example, if Σ = and 0 < 1, then the lexicographical order on Σ* includes the relationships ε < 0 < 00 < 000 < ... < 0001 < 001 < 01 < 010 < 011 < 0110 < 01111 < 1 < 10 < 100 < 101 < 111 < 1111 < 11111 ... The lexicographical order is total order, total if the alphabetical order is, but isn't well-founded for any nontrivial alphabet, even if the alphabetical order is. See Shortlex for an alternative string ordering that preserves well-foundedness.


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 ''k'' is the number of symbols in Σ: * Fixed-length strings of length ''n'' can be viewed as the integer locations in an ''n''-dimensional hypercube with sides of length ''k''-1. * Variable-length strings (of finite length) can be viewed as nodes on a k-ary tree, perfect ''k''-ary tree. * Infinite strings (otherwise not considered here) can be viewed as infinite paths on a ''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, ''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.


See also

* Binary-safe — a property of string manipulating functions treating their input as raw data stream * Bit array — a string of binary digits *
C string handling The C programming language has a set of functions implementing operations on strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other ...
— overview of C string handling * C++ string handling — overview of C++ string handling * Comparison of programming languages (string functions) * Connection string — passed to a driver to initiate a connection (e.g., to a database) * Empty string — its properties and representation in programming languages * Incompressible string — a string that cannot be compressed by any algorithm * Rope (data structure) — a data structure for efficiently manipulating long strings * String metric — notions of similarity between strings


References

{{Formal languages and grammars , state=collapsed String (computer science), Character encoding Data types Formal languages Combinatorics on words Primitive types Syntactic entities Algorithms on strings