View source for String (computer science)

{{Short description|Sequence of characters, data type}}
[[File:String example.png|alt=Diagram of String data in computing. Shows the word "example" with each letter in a separate box. The word "String" is above, referring to the entire sentence. The label "Character" is below and points to an individual box.|thumb|Strings are typically made up of [[Character (computing)|characters]], and are often used to store human-readable data, such as words or sentences.]]

In [[Computer programming|computer programming]], a '''string''' is traditionally a [[Sequence|sequence]] of [[Character (computing)|characters]], either as a [[Literal (computer programming)|literal constant]] or as some kind of [[Variable (computer science)|variable]]. The latter may allow its elements to be [[Immutable object|mutated]] and the length changed, or it may be fixed (after creation). A string is generally considered as a [[Data type|data type]] and is often implemented as an [[Array data structure|array data structure]] of [[Byte|byte]]s (or [[Word (computer architecture)|word]]s) that stores a sequence of elements, typically characters, using some [[Character encoding|character encoding]]. ''String'' may also denote more general [[Array data type|arrays]] or other sequence (or [[List (abstract data type)|list]]) 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 to allow it to hold a variable number of elements.

When a string appears literally in [[Source code|source code]], it is known as a [[String literal|string literal]] or an anonymous string.<ref>{{cite web|url=http://www.acsu.buffalo.edu/~fineberg/mfc158/week10lecture.htm|title=Introduction To Java – MFC 158 G|quote=String literals (or constants) are called ‘anonymous strings’|url-status=live|archive-url=https://web.archive.org/web/20160303233357/http://www.acsu.buffalo.edu/~fineberg/mfc158/week10lecture.htm|archive-date=2016-03-03}}</ref>

In [[Formal language|formal language]]s, which are used in [[Mathematical logic|mathematical logic]] and [[Theoretical computer science|theoretical computer science]], a string is a finite sequence of [[Symbol (formal)|symbol]]s that are chosen from a [[Set (mathematics)|set]] called an alphabet.

== Purpose ==

A primary purpose of strings is to store human-readable text, like words and sentences. Strings are used to communicate information from a computer program to the user of the program.<ref>{{cite web |url=https://users.cs.utah.edu/~germain/PPS/Topics/strings.html |website=University of Utah, Kahlert School of Computing |title=Strings
 |first=H. James |last=de St. Germain }}</ref> A program may also accept string input from its user. Further, strings may store data expressed as characters yet not intended for human reading.

Example strings and their purposes:

* A message like "<code>file upload complete</code>" is a string that software shows to [[End user|end user]]s. In the program's [[Source code|source code]], this message would likely appear as a [[String literal|string literal]].
* User-entered text, like "<code>I got a new job today</code>" as a status update on a [[Social:Social media|social media]] service. Instead of a string literal, the software would likely store this string in a [[Database|database]].
* Alphabetical data, like "<code>AGATGCCGT</code>" representing nucleic acid sequences of [[Biology:DNA|DNA]].<ref>{{cite web |url=https://plant-breeding-genomics.extension.org/dna-as-a-biochemical-entity-and-data-string/ |title=DNA as a Biochemical Entity and Data String |date=November 14, 2019 |first1=David M. |last1=Francis |first2=Heather L. |last2=Merk }}</ref>
* Computer settings or parameters, like "<code>?action=edit</code>" as a URL [[Query string|query string]]. Often these are intended to be somewhat human-readable, though their primary purpose is to communicate to computers.

The term string may also designate a sequence of data or computer records other than characters {{mdash}} like a "string of [[Bit|bit]]s" {{mdash}} but when used without qualification it refers to strings of characters.<ref name=Burchfield1986 />

==History==

Use of the word "string" to mean any items arranged in a line, series or succession dates back centuries.<ref>{{cite encyclopedia |encyclopedia=The Oxford English Dictionary |volume=X |publisher=Oxford at the Clarendon Press |year=1933 |title=string }}</ref><ref>{{cite web |title=string (n.) |url=https://www.etymonline.com/search?q=string |website=Online Etymology Dictionary }}</ref> In 19th-Century typesetting, compositors used the term "string" to denote a length of type printed on paper; the string would be measured to determine the compositor's pay.<ref>{{cite encyclopedia |encyclopedia=The Century Dictionary |author-link2=Benjamin Eli Smith |first1=William Dwight |last1=Whitney |first2=Benjamin E. |last2=Smith |publisher=The Century Company |location=New York |page=5994 |title=string }}</ref><ref name=Burchfield1986 /><ref>{{cite news |newspaper=Milwaukee Sentinel |date=January 11, 1898 |title=Old Union's Demise |page=3 }}</ref>

Use of the word "string" to mean "a sequence of symbols or linguistic elements in a definite order" emerged from mathematics, symbolic logic, and linguistic theory to speak about the [[Formal system|formal]] behavior of symbolic systems, setting aside the symbols' meaning.<ref name=Burchfield1986>{{cite encyclopedia |title=string |encyclopedia=A Supplement to the Oxford English Dictionary |year=1986 |last=Burchfield |first=R.W. |publisher=Oxford at the Clarendon Press |}}</ref>

For example, logician [[Biography:C. I. Lewis|C. I. Lewis]] wrote in 1918:<ref>{{cite book |title=A survey of symbolic logic |location=Berkeley |publisher=University of California Press |year=1918 |page=355 |last=Lewis |first=C.I. |url=https://archive.org/details/asurveyofsymboli00lewiuoft/page/355/mode/1up }}</ref>
<blockquote>
A mathematical system is any set of strings of recognisable marks in which some of the strings are taken initially and the remainder derived from these by operations performed according to rules which are independent of any meaning assigned to the marks. That a system should consist of 'marks' instead of sounds or odours is immaterial.
</blockquote>

According to [[Biography:Jean E. Sammet|Jean E. Sammet]], "the first realistic string handling and pattern matching language" for computers was [[COMIT]] in the 1950s, followed by the [[SNOBOL]] language of the early 1960s.<ref>{{cite journal |url=https://redirect.cs.umbc.edu/courses/undergraduate/331/resources/papers/sammet1972.pdf |journal=Communications of the ACM |first=Jean E. |last=Sammet |title=Programming Languages: History and Future |date=July 1972 |volume=15 |number=7 |doi=10.1145/361454.361485 |s2cid=2003242 }}</ref>

== 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|programming language]]. In some languages they are available as primitive types and in others as composite types. The [[Philosophy:Syntax|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|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 size of available [[Computer memory|computer 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 [[Software:EBCDIC|EBCDIC]]. If text in one encoding was displayed on a system using a different encoding, text was often [[Mojibake|mangled]], though often somewhat readable and some computer users learned to read the mangled text.

Logographic languages such as [[Social:Chinese language|Chinese]], [[Social:Japanese language|Japanese]], and [[Social:Korean language|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 [[Extended Unix Code|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 ===
{{anchor|String Buffers}}
Some languages, such as [[C++]], [[Perl]] and [[Ruby (programming language)|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 (programming language)|Java]], [[JavaScript]], [[Lua (programming language)|Lua]], [[Python (programming language)|Python]], and [[Go (programming language)|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 {{Javadoc:SE|java/lang|StringBuilder}}, the thread-safe Java {{Javadoc:SE|java/lang|StringBuffer}}, and the Cocoa <code>NSMutableString</code>. There are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completely [[Thread safety|thread-safe]].

Strings are typically implemented as [[Array data type|arrays]] 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 (programming language)|Haskell]] implement them as linked lists instead.

Some languages, such as [[Prolog]] and [[Erlang (programming language)|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 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 data type|array]]s 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.

==== Null-terminated ====
{{Main|Null-terminated string}}

The length of a string can be stored implicitly by using a special terminating character; often this is the [[Null character|null character]] (NUL), which has all bits zero, a convention used and perpetuated by the popular [[C (programming language)|C programming language]].<ref>
{{Citation
 |last1        = Bryant
 |first1       = Randal E.
 |last2       = David
 |first2      = O'Hallaron
 |title       = Computer Systems: A Programmer's Perspective
 |place       = Upper Saddle River, NJ
 |publisher   = Pearson Education
 |year        = 2003
 |edition     = 2003
 |url         = http://csapp.cs.cmu.edu/
 |isbn        = 0-13-034074-X
 |page        = 40
 |url-status     = live
 |archive-url  = https://web.archive.org/web/20070806075942/http://csapp.cs.cmu.edu/
 |archive-date = 2007-08-06
}}
</ref> 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 structure|implicit data structure]].

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

An example of a ''null-terminated string'' stored in a 10-byte buffer, along with its [[ASCII]] (or more modern [[UTF-8]]) representation as 8-bit hexadecimal numbers is:

{| class="wikitable" style="margin-left: auto; margin-right:auto"
 |-
 | <code>F</code>  || <code>R</code>  || <code>A</code>  || <code>N</code>  || <code>K</code>
 | <small>[[Null character|NUL]]</small>
 | style="background: #DDD" | <code style="background: #DDD">k</code>
 | style="background: #DDD" | <code style="background: #DDD">e</code>
 | style="background: #DDD" | <code style="background: #DDD">f</code>
 | style="background: #DDD" | <code style="background: #DDD">w</code>
 |-
 | 46<sub>[[Hexadecimal#Using 0–9 and A–F|16]]</sub> || 52<sub>16</sub> || 41<sub>16</sub> || 4E<sub>16</sub> || 4B<sub>16</sub>
 | 00<sub>16</sub>
 | style="background: #DDD" | 6B<sub>16</sub>
 | style="background: #DDD" | 65<sub>16</sub>
 | style="background: #DDD" | 66<sub>16</sub>
 | style="background: #DDD" | 77<sub>16</sub>
 |}

The length of the string in the above example, "<code>FRANK</code>", 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|assembly language]] 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. <code>$</code> was used by many assembler systems, <code>:</code> used by [[Company:Control Data Corporation|CDC]] systems (this character had a value of zero), and the [[Engineering:ZX80|ZX80]] used <code>"</code><ref name=asm>{{cite web|last1=Wearmouth |first1=Geoff |title=An Assembly Listing of the ROM of the Sinclair ZX80 |url=http://www.wearmouth.demon.co.uk/zx80.htm |url-status=unfit |archive-url=https://web.archive.org/web/20150815035611/http://www.wearmouth.demon.co.uk/zx80.htm |archive-date=August 15, 2015 }}</ref> since this was the string delimiter in its BASIC language.

Somewhat similar, "data processing" machines like the IBM 1401 used a special [[Word mark (computer hardware)|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.<ref>{{cite web |last1=Allison |first1=Dennis |title=Design Notes for Tiny BASIC |url=http://www.ittybittycomputers.com/IttyBitty/TinyBasic/DDJ1/Design.html |url-status=live |archive-url=https://web.archive.org/web/20170410220759/http://www.ittybittycomputers.com/IttyBitty/TinyBasic/DDJ1/Design.html |archive-date=2017-04-10 }}</ref>

==== 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 (programming language)|Pascal]] 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 to store the string length. When the ''length'' field covers the [[Address space|address space]], strings are limited only by the [[Dynamic memory allocation|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 structure|implicit data structure]], 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 does not 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.<!---commented out: "bad" is not an issue in a technical encyclopedic article---This in itself is not that bad since the number of bytes is just logarithmic on the length of string,---><!---commented out: while NULL-terminated string allow for pointers to proper substrings, length-prefixed strings do not; a pointer to a length-prefixed string has to point to the length field, which remains at the same location after growing--- but the downside is that any direct pointers to the string data get invalidated (they should move by one).--->

Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:

{| class="wikitable" style="margin-left: auto; margin-right:auto"
 |-
 | <small>length</small>
 | <code>F</code>  || <code>R</code>  || <code>A</code>  || <code>N</code>  || <code>K</code>
 | style="background: #DDD" | <code style="background: #DDD">k</code>
 | style="background: #DDD" | <code style="background: #DDD">e</code>
 | style="background: #DDD" | <code style="background: #DDD">f</code>
 | style="background: #DDD" | <code style="background: #DDD">w</code>
 |-
 | 05<sub>16</sub>
 | 46<sub>16</sub> || 52<sub>16</sub> || 41<sub>16</sub> || 4E<sub>16</sub> || 4B<sub>16</sub>
 | style="background: #DDD" | 6B<sub>16</sub>
 | style="background: #DDD" | 65<sub>16</sub>
 | style="background: #DDD" | 66<sub>16</sub>
 | style="background: #DDD" | 77<sub>16</sub>
 |}

==== Strings as records ====
Many languages, including object-oriented ones, implement strings as [[Record (computer science)|record]]s with an internal structure like:

<source lang="cpp">
class string {
  size_t length;
  char *text;
};
</source>

However, since the implementation is usually [[Information hiding|hidden]], the string must be accessed and modified through member functions. <code>text</code> is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also string (C++).

==== 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 handling|C string]] 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]] (replacing repeated characters by the character value and a length) and Hamming encoding{{ clarify | date = June 2015 | reason = did you mean Huffman compression? Or do we need a few more words about error correction coding here? I don't see how either one helps us find out how long the string is. }}.

While these representations are common, others are possible. Using [[Rope (data structure)|rope]]s makes certain string operations, such as insertions, deletions, and concatenations more efficient.

The core data structure in a [[Software:Text editor|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|gap buffer]], a linked list of lines, a [[Piece table|piece table]], or a [[Rope (data structure)|rope]]—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.<ref>
Charles Crowley.
[http://www.cs.unm.edu/~crowley/papers/sds.pdf "Data Structures for Text Sequences"] {{webarchive|url=https://web.archive.org/web/20160304042917/https://www.cs.unm.edu/~crowley/papers/sds.pdf |date=2016-03-04 }}.
Section
[http://www.cs.unm.edu/~crowley/papers/sds/node1.html "Introduction"] {{webarchive|url=https://web.archive.org/web/20160404020539/http://www.cs.unm.edu/~crowley/papers/sds/node1.html |date=2016-04-04 }}.
</ref>

=== 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|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|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 [[Improper input validation|limited or no validation]] of user input can cause a program to be vulnerable to [[Code injection|code injection]] attacks.

== Literal strings ==
{{Main|String literal}}

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 does not 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 marks (ASCII [[Hexadecimal#Using 0–9 and A–F|0x22]] double quote <code>"str"</code> or ASCII 0x27 single quote <code>'str'</code>), 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 character|escape sequence]]s are often available, usually prefixed with the backslash character (ASCII 0x5C).
* Terminated by a newline sequence, for example in Windows [[INI file]]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 or byte string, for example, may be used to represent non-textual [[Binary data|binary 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. If the programming language's string implementation is not [[8-bit clean|8-bit clean]], 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]] functions on such a "byte string" often seems to work, but later leads to security problems.<ref>
[https://www.sudo.ws/todd/papers/strlcpy.html "strlcpy and strlcat - consistent, safe, string copy and concatenation."] {{webarchive|url=https://web.archive.org/web/20160313163321/https://www.sudo.ws/todd/papers/strlcpy.html |date=2016-03-13 }}
</ref><ref>
[http://udel.edu/~pconrad/UnixAtUD/strcpy.html "A rant about strcpy, strncpy and strlcpy."] {{webarchive|url=https://web.archive.org/web/20160229080205/http://udel.edu/~pconrad/UnixAtUD/strcpy.html |date=2016-02-29 }}
</ref><ref>
Keith Thompson.
"No, strncpy() is not a "safer" strcpy()".
2012.
</ref>

== String processing algorithms ==
There are many [[Algorithm|algorithm]]s for processing strings, each with various trade-offs. Competing algorithms can be [[Analysis of algorithms|analyzed]] with respect to run time, storage requirements, and so forth. The name '''stringology''' was coined in 1984 by computer scientist [[Biography:Zvi Galil|Zvi Galil]] for the theory of algorithms and data structures used for string processing.<ref>{{cite web|url=http://www.stringology.org/|title=The Prague Stringology Club|work=stringology.org|access-date=23 May 2015|url-status=live|archive-url=https://web.archive.org/web/20150601001757/http://www.stringology.org/|archive-date=1 June 2015}}</ref><ref>{{cite web |last1=Evarts |first1=Holly |title=Former Dean Zvi Galil Named a Top 10 Most Influential Computer Scientist in the Past Decade |url=https://www.engineering.columbia.edu/news/zvi-galil-top-10-computer-scientist |website=Columbia Engineering |language=en |date=18 March 2021 |quote=He invented the terms 'stringology,' which is a subfield of string algorithms,}}</ref><ref>{{cite book |last1=Crochemore |first1=Maxime |title=Jewels of stringology |date=2002 |location=Singapore |isbn=981-02-4782-6 |page=v |quote=The term stringology is a popular nickname for string algorithms as well as for text algorithms.}}</ref>

Some categories of algorithms include:
* String searching algorithms for finding a given substring or pattern
* String manipulation algorithms
* [[Sorting algorithm]]s
* [[Regular expression]] algorithms
* Parsing a string
* Sequence mining

Advanced string algorithms often employ complex mechanisms and data structures, among them [[Suffix tree|suffix tree]]s and [[Finite-state machine|finite-state machine]]s.

== 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]]
* [[Icon (programming language)|Icon]]
* [[MUMPS]]
* [[Perl]]
* [[Rexx]]
* [[Ruby (programming language)|Ruby]]
* [[Sed|sed]]
* [[SNOBOL]]
* [[Tcl]]
* [[TTM (programming language)|TTM]]

Many [[Software:Unix|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|API]]s like Multimedia Control Interface, [[Embedded SQL|embedded SQL]] or [[Printf|printf]] use strings to hold commands that will be interpreted.

Many scripting programming languages, including Perl, [[Python (programming language)|Python]], Ruby, and Tcl employ [[Regular expression|regular expression]]s to facilitate text operations. Perl is particularly noted for its regular expression use,<ref>{{cite web|url=http://cslibrary.stanford.edu/108/EssentialPerl.html#re|title=Essential Perl|quote=Perl's most famous strength is in string manipulation with regular expressions.|url-status=live|archive-url=https://web.archive.org/web/20120421014328/http://cslibrary.stanford.edu/108/EssentialPerl.html#re|archive-date=2012-04-21}}</ref> and many other languages and applications implement [[Software:Perl Compatible Regular Expressions|Perl compatible regular expression]]s.

Some languages such as Perl and Ruby support [[String interpolation|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 <code>[[Comparison of programming languages (string functions)#length|length]]</code> or <code>len</code>. For example, <code>length("hello world")</code> would return 11. Another common function is [[Concatenation|concatenation]], where a new string is created by appending two strings, often this is the + addition operator.

Some [[Engineering:Microprocessor|microprocessor]]'s [[Instruction set architecture|instruction set architecture]]s contain direct support for string operations, such as block copy (e.g. In intel x86m <code>REPNZ MOVSB</code>).<ref>{{cite web|url=https://docs.oracle.com/cd/E19120-01/open.solaris/817-5477/eoizn/index.html|title=x86 string instructions|url-status=live|archive-url=https://web.archive.org/web/20150327220944/http://docs.oracle.com/cd/E19120-01/open.solaris/817-5477/eoizn/index.html|archive-date=2015-03-27}}</ref>

== Formal theory ==

Let Σ be a [[Finite set|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|sequence]] of symbols from Σ.<ref name="partee">{{cite book |author1=Barbara H. Partee |author2=Alice ter Meulen|author3=Robert E. Wall |title=Mathematical Methods in Linguistics |publisher=Kluwer |year=1990}}</ref> For example, if Σ = {0,&nbsp;1}, then ''01011'' is a string over Σ.

The ''[[Physics:Length|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|empty string]]'' is the unique string over Σ of length 0, and is denoted ''ε'' or ''λ''.<ref name="partee"/><ref>{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}} Here: sect.1.1, p.1</ref>

The set of all strings over Σ of length ''n'' is denoted Σ<sup>''n''</sup>.  For example, if Σ = {0, 1}, then Σ<sup>2</sup> = {00, 01, 10, 11}.  We have Σ<sup>0</sup> = {ε} for every alphabet Σ.

The set of all strings over Σ of any length is the [[Kleene star|Kleene closure]] of Σ and is denoted Σ<sup>*</sup>.  In terms of Σ<sup>''n''</sup>,
:<math>\Sigma^{*} = \bigcup_{n \in \mathbb{N} \cup \{0\}} \Sigma^{n}</math>
For example, if Σ = {0, 1}, then Σ<sup>*</sup> = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}.  Although the set Σ<sup>*</sup> itself is countably infinite, each element of Σ<sup>*</sup> is a string of finite length.

A set of strings over Σ (i.e. any [[Subset|subset]] of Σ<sup>*</sup>) is called a ''[[Formal language|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|binary operation]] on Σ<sup>*</sup>.  For any two strings ''s'' and ''t'' in Σ<sup>*</sup>, 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 Σ = {a, b, ..., z}, ''s''&nbsp;=&nbsp;{{code|bear}}, and ''t''&nbsp;=&nbsp;{{code|hug}}, then ''st''&nbsp;=&nbsp;{{code|bearhug}} and ''ts''&nbsp;=&nbsp;{{code|hugbear}}.

String concatenation is an associative, but non-commutative operation. The empty string ε serves as the [[Identity element|identity element]]; for any string ''s'', ε''s'' = ''s''ε = ''s''.  Therefore, the set Σ<sup>*</sup> and the concatenation operation form a [[Monoid|monoid]], the [[Free monoid|free monoid]] generated by Σ.  In addition, the length function defines a monoid homomorphism from Σ<sup>*</sup> to the non-negative integers (that is, a function <math>L: \Sigma^{*} \mapsto \mathbb{N} \cup \{0\}</math>, such that <math>L(st)=L(s)+L(t)\quad \forall s,t\in\Sigma^*</math>).

A string ''s'' is said to be a ''[[Substring|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 Σ<sup>*</sup>, 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 order|prefix order]]s.

=== 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, 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 Σ = {0, 1} 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|total order]] (cf. [[Social:Alphabetical order|alphabetical order]]) one can define a total order on Σ<sup>*</sup> called [[Lexicographical order|lexicographical order]]. The lexicographical order is [[Total order|total]] if the alphabetical order is, but is not well-founded for any nontrivial alphabet, even if the alphabetical order is. For example, if Σ = {0, 1} and 0 < 1, then the lexicographical order on Σ<sup>*</sup> includes the relationships ε < 0 < 00 < 000 < ... < 0001 < ... < 001 < ... < 01 < 010 < ... < 011 < 0110 < ... < 01111 < ... < 1 < 10 < 100 < ... < 101 < ... < 111 < ... < 1111 < ... < 11111 ... With respect to this ordering, e.g. the infinite set { 1, 01, 001, 0001, 00001, 000001, ... } has no minimal element.

See Shortlex for an alternative string ordering that preserves well-foundedness.
For the example alphabet, the shortlex order is ε < 0 < 1 < 00 < 01 < 10 < 11 < 000 < 001 < 010 < 011 < 100 < 101 < 0110 < 111 < 0000 < 0001 < 0010 < 0011 < ... < 1111 < 00000 < 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|string operations]].

=== Topology ===
[[File:Hamming distance 3 bit binary.svg|thumb|150px|(Hyper)cube of binary strings of length 3]]
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|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|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|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.

[[Isomorphism]]s 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]] — 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 ==
{{Reflist}}

{{Strings}}
{{Data types}}
{{Formal languages and grammars |state=collapsed}}

[[Category:String (computer science)| ]]
[[Category:Character encoding]]
[[Category:Data types]]
[[Category:Formal languages]]
[[Category:Primitive types]]
[[Category:Algorithms on strings]]

{{Sourceattribution|String (computer science)}}