{"history":[],"article":{"id":"a0758c6e-6f48-441b-a7ed-8ccd34e6ef64","title":"String (computer science)","slug":"string-computer-science","content":":::summary\n:::\n\n# \nIn [computer programming](https://bliptext.com/articles/computer-programming), a **string** is traditionally a [sequence](https://bliptext.com/articles/sequence) of [characters](https://bliptext.com/articles/character-computing), either as a [literal constant](https://bliptext.com/articles/literal-computer-programming) or as some kind of [variable](https://bliptext.com/articles/variable-computer-science).\nThe latter may allow its elements to be [mutated](https://bliptext.com/articles/immutable-object) and the length changed, or it may be fixed (after creation).\nA string is generally considered as a [data type](https://bliptext.com/articles/data-type) and is often implemented as an [array data structure](https://bliptext.com/articles/array-data-structure) of [bytes](https://bliptext.com/articles/byte) (or [words](https://bliptext.com/articles/word-computer-architecture)) that stores a sequence of elements, typically characters, using some [character encoding](https://bliptext.com/articles/character-encoding).\nString may also denote more general [arrays](https://bliptext.com/articles/array-data-type) or other sequence (or [list](https://bliptext.com/articles/list-abstract-data-type)) data types and structures.\nDepending on the programming language and precise data type used, a [variable](https://bliptext.com/articles/variable-programming) declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ [dynamic allocation](https://bliptext.com/articles/dynamic-allocation) to allow it to hold a [variable](https://bliptext.com/articles/variable-programming) number of elements.\nWhen a string appears literally in [source code](https://bliptext.com/articles/source-code), it is known as a [string literal](https://bliptext.com/articles/string-literal) or an anonymous string.\nIn [formal languages](https://bliptext.com/articles/formal-language), which are used in [mathematical logic](https://bliptext.com/articles/mathematical-logic) and [theoretical computer science](https://bliptext.com/articles/theoretical-computer-science), a string is a finite sequence of [symbols](https://bliptext.com/articles/symbol-formal) that are chosen from a [set](https://bliptext.com/articles/set-mathematics) called an [alphabet](https://bliptext.com/articles/alphabet-computer-science).\n# [Strings are typically made up of characters, and are often used to store human-readable data, such as words or sentences. | upload.wikimedia.org/wikipedia/commons/6/6b/String///example.png]\n\n# Purpose\nA primary purpose of strings is to store human-readable text, like words and sentences.\nStrings are used to communicate information from a computer program to the user of the program.\nA program may also accept string input from its user.\nFurther, strings may store data expressed as characters yet not intended for human reading.\nExample strings and their purposes:\nThe term string may also designate a sequence of data or computer records other than characters — like a \"string of [bits](https://bliptext.com/articles/bit)\" — but when used without qualification it refers to strings of characters.\n\n# History\nUse of the word \"string\" to mean any items arranged in a line, series or succession dates back centuries.\nIn 19th-Century typesetting, [compositors](https://bliptext.com/articles/compositor-typesetting) used the term \"string\" to denote a length of type printed on paper; the string would be measured to determine the compositor's pay.\nUse of the word \"string\" to mean \"a sequence of symbols or linguistic elements in a definite order\" emerged from mathematics, [symbolic logic](https://bliptext.com/articles/symbolic-logic), and [linguistic theory](https://bliptext.com/articles/linguistic-theory) to speak about the [formal](https://bliptext.com/articles/formal-system) behavior of symbolic systems, setting aside the symbols' meaning.\nFor example, logician [C. I. Lewis](https://bliptext.com/articles/c-i-lewis) wrote in 1918:\nA 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.\nThat a system should consist of 'marks' instead of sounds or odours is immaterial.\nAccording to [Jean E. Sammet](https://bliptext.com/articles/jean-e-sammet), \"the first realistic string handling and pattern matching language\" for computers was [COMIT](https://bliptext.com/articles/comit) in the 1950s, followed by the [SNOBOL](https://bliptext.com/articles/snobol) language of the early 1960s.\n\n# String datatypes\nA **string datatype** is a datatype modeled on the idea of a formal string.\nStrings are such an important and useful datatype that they are implemented in nearly every [programming language](https://bliptext.com/articles/programming-language).\nIn some languages they are available as [primitive types](https://bliptext.com/articles/primitive-type) and in others as [composite types](https://bliptext.com/articles/composite-type).\nThe [syntax](https://bliptext.com/articles/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.\n\n## String length\nAlthough formal strings can have an arbitrary finite length, the length of strings in real languages is often constrained to an artificial maximum.\nIn general, there are two types of string datatypes: fixed-length strings, which have a fixed maximum length to be determined at [compile time](https://bliptext.com/articles/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](https://bliptext.com/articles/memory-management)).\nMost strings in modern [programming languages](https://bliptext.com/articles/programming-languages) are variable-length strings.\nOf course, even variable-length strings are limited in length – by the size of available [computer memory](https://bliptext.com/articles/computer-memory).\nThe 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.\nSee also \"[Null-terminated](https://bliptext.com/articles/)\" below.\n\n## Character encoding\nString 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.\nThese character sets were typically based on [ASCII](https://bliptext.com/articles/ascii) or [EBCDIC](https://bliptext.com/articles/ebcdic).\nIf text in one encoding was displayed on a system using a different encoding, text was often [mangled](https://bliptext.com/articles/mojibake), though often somewhat readable and some computer users learned to read the [mangled](https://bliptext.com/articles/mojibake) text.\n[Logographic](https://bliptext.com/articles/logograph) languages such as [Chinese](https://bliptext.com/articles/chinese-language), [Japanese](https://bliptext.com/articles/japanese-language), and [Korean](https://bliptext.com/articles/korean-language) (known collectively as [CJK](https://bliptext.com/articles/cjk-characters)) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation.\nThe normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK [ideographs](https://bliptext.com/articles/ideographs).\nUse 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.\nSome encodings such as the [EUC](https://bliptext.com/articles/extended-unix-code) 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.\nOther encodings such as [ISO-2022](https://bliptext.com/articles/iso-2022) and [Shift-JIS](https://bliptext.com/articles/shift-jis) do not make such guarantees, making matching on byte codes unsafe.\nThese 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.\n[Unicode](https://bliptext.com/articles/unicode) has simplified the picture somewhat.\nMost programming languages now have a datatype for Unicode strings.\nUnicode's preferred byte stream format [UTF-8](https://bliptext.com/articles/utf-8) is designed not to have the problems described above for older multibyte encodings.\nUTF-8, UTF-16 and [UTF-32](https://bliptext.com/articles/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](https://bliptext.com/articles/utf-32) does make code points fixed-sized, but these are not \"characters\" due to composing codes).\n\n## Implementations\nSome languages, such as [C++](https://bliptext.com/articles/c), [Perl](https://bliptext.com/articles/perl) and [Ruby](https://bliptext.com/articles/ruby-programming-language), normally allow the contents of a string to be changed after it has been created; these are termed mutable strings.\nIn other languages, such as [Java](https://bliptext.com/articles/java-programming-language), [Java](https://bliptext.com/articles/java-programming-language)Script, [Lua](https://bliptext.com/articles/lua-programming-language), [Python](https://bliptext.com/articles/python-programming-language), and [Go](https://bliptext.com/articles/go-programming-language), the value is fixed and a new string must be created if any alteration is to be made; these are termed immutable strings.\nSome of these languages with immutable strings also provide another type that is mutable, such as Java and [.NET](https://bliptext.com/articles/net-framework)'s, the thread-safe Java , and the [Cocoa](https://bliptext.com/articles/cocoa-api).\nThere are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completely [thread-safe](https://bliptext.com/articles/thread-safety).\nStrings are typically implemented as [arrays](https://bliptext.com/articles/array-data-type) 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.\nA few languages such as [Haskell](https://bliptext.com/articles/haskell-programming-language) implement them as [linked lists](https://bliptext.com/articles/linked-list) instead.\nA lot of high-level languages provide strings as a primitive data type, such as [JavaScript](https://bliptext.com/articles/javascript) and [PHP](https://bliptext.com/articles/php), while most others provide them as a composite data type, some with special language support in writing literals, for example, [Java](https://bliptext.com/articles/java-programming-language) and [C#](https://bliptext.com/articles/c-sharp-programming-language).\nSome languages, such as [C](https://bliptext.com/articles/c-programming-language), [Prolog](https://bliptext.com/articles/prolog) and [Erlang](https://bliptext.com/articles/erlang-programming-language), avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes.\nEven in programming languages having a dedicated string type, string can usually be iterated as a sequence character codes, like lists of integers or other values.\n\n## Representations\nRepresentations of strings depend heavily on the choice of character repertoire and the method of character encoding.\nOlder string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the [ISO 8859](https://bliptext.com/articles/iso-8859) series.\nModern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16.\nThe term byte string usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such.\nByte 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.\nMost string implementations are very similar to variable-length [arrays](https://bliptext.com/articles/array-data-type) with the entries storing the [character codes](https://bliptext.com/articles/character-code) of corresponding characters.\nThe principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array.\nThis happens for example with UTF-8, where single codes ([UCS](https://bliptext.com/articles/universal-character-set) code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes.\nIn these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use).\n[UTF-32](https://bliptext.com/articles/utf-32) avoids the first part of the problem.\n\n### Null-terminated\nThe length of a string can be stored implicitly by using a special terminating character; often this is the [null character](https://bliptext.com/articles/null-character) (NUL), which has all bits zero, a convention used and perpetuated by the popular [C programming language](https://bliptext.com/articles/c-programming-language).\nHence, this representation is commonly referred to as a **C string**.\nThis representation of an n-character string takes n + 1 space (1 for the terminator), and is thus an [implicit data structure](https://bliptext.com/articles/implicit-data-structure).\nIn terminated strings, the terminating code is not an allowable character in any string.\nStrings with length field do not have this limitation and can also store arbitrary [binary data](https://bliptext.com/articles/binary-data).\nAn example of a null-terminated string stored in a 10-byte [buffer](https://bliptext.com/articles/buffer-computer-science), along with its [ASCII](https://bliptext.com/articles/ascii) (or more modern [UTF-8](https://bliptext.com/articles/utf-8)) representation as 8-bit [hexadecimal numbers](https://bliptext.com/articles/hexadecimal-number) is:\nThe length of the string in the above example, \" \", is 5 characters, but it occupies 6 bytes.\nCharacters after the terminator do not form part of the representation; they may be either part of other data or just garbage.\n(Strings of this form are sometimes called ASCIZ strings, after the original [assembly language](https://bliptext.com/articles/assembly-language) directive used to declare them.)\n\n### Byte- and bit-terminated\nUsing 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.\nwas used by many assembler systems, used by [CDC](https://bliptext.com/articles/control-data-corporation) systems (this character had a value of zero), and the [ZX80](https://bliptext.com/articles/zx80) used since this was the string delimiter in its BASIC language.\nSomewhat similar, \"data processing\" machines like the [IBM 1401](https://bliptext.com/articles/ibm-1401) used a special [word mark](https://bliptext.com/articles/word-mark-computer-hardware) bit to delimit strings at the left, where the operation would start at the right.\nThis bit had to be clear in all other parts of the string.\nThis 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.\nEarly 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.\nIt must be reset to 0 prior to output.\n\n### Length-prefixed\nThe length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value.\nThis convention is used in many [Pascal](https://bliptext.com/articles/pascal-programming-language) dialects; as a consequence, some people call such a string a **[Pascal](https://bliptext.com/articles/pascal-programming-language) string** or **P-string**.\nStoring the string length as byte limits the maximum string length to 255.\nTo avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit [words](https://bliptext.com/articles/word-data-type) to store the string length.\nWhen the length field covers the [address space](https://bliptext.com/articles/address-space), strings are limited only by the [available memory](https://bliptext.com/articles/dynamic-memory-allocation).\nIf the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an [implicit data structure](https://bliptext.com/articles/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.).\nIf the length is not bounded, encoding a length n takes log(n) space (see [fixed-length code](https://bliptext.com/articles/fixed-length-code)), so length-prefixed strings are a [succinct data structure](https://bliptext.com/articles/succinct-data-structure), encoding a string of length n in log(n) + n space.\nIn 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.\nHere is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:\n\n### Strings as records\nMany languages, including object-oriented ones, implement strings as [records](https://bliptext.com/articles/record-computer-science) with an internal structure like:\nHowever, since the implementation is usually [hidden](https://bliptext.com/articles/information-hiding), the string must be accessed and modified through member functions.\nis a pointer to a dynamically allocated memory area, which might be expanded as needed.\nSee also [string (C++)](https://bliptext.com/articles/string-c).\n\n### Other representations\nBoth character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by [C string](https://bliptext.com/articles/c-string-handling) library functions: Strings using a length code are limited to the maximum value of the length code.\nBoth of these limitations can be overcome by clever programming.\nIt 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.\nIt is also possible to optimize the string represented using techniques from [run length encoding](https://bliptext.com/articles/run-length-encoding) (replacing repeated characters by the character value and a length) and [Hamming encoding](https://bliptext.com/articles/hamming-coding).\nWhile these representations are common, others are possible.\nUsing [ropes](https://bliptext.com/articles/rope-data-structure) makes certain string operations, such as insertions, deletions, and concatenations more efficient.\nThe core data structure in a [text editor](https://bliptext.com/articles/text-editor) is the one that manages the string (sequence of characters) that represents the current state of the file being edited.\nWhile 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](https://bliptext.com/articles/gap-buffer), a [linked list](https://bliptext.com/articles/linked-list) of lines, a [piece table](https://bliptext.com/articles/piece-table), or a [rope](https://bliptext.com/articles/rope-data-structure)—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.\n\n## Security concerns\nThe differing memory layout and storage requirements of strings can affect the security of the program accessing the string data.\nString representations requiring a terminating character are commonly susceptible to [buffer overflow](https://bliptext.com/articles/buffer-overflow) problems if the terminating character is not present, caused by a coding error or an [attacker](https://bliptext.com/articles/hacker-computer-security) deliberately altering the data.\nString representations adopting a separate length field are also susceptible if the length can be manipulated.\nIn such cases, program code accessing the string data requires [bounds checking](https://bliptext.com/articles/bounds-checking) to ensure that it does not inadvertently access or change data outside of the string memory limits.\nString data is frequently obtained from user input to a program.\nAs such, it is the responsibility of the program to validate the string to ensure that it represents the expected format.\nPerforming [limited or no validation](https://bliptext.com/articles/improper-input-validation) of user input can cause a program to be vulnerable to [code injection](https://bliptext.com/articles/code-injection) attacks.\n\n# Literal strings\nSometimes, strings need to be embedded inside a text file that is both human-readable and intended for consumption by a machine.\nThis is needed in, for example, source code of programming languages, or in configuration files.\nIn 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.\nStoring the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone.\nTwo common representations are:\n\n# Non-text strings\nWhile character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data.\nA [bit string](https://bliptext.com/articles/bit-string) or [byte string](https://bliptext.com/articles/byte-string), for example, may be used to represent non-textual [binary data](https://bliptext.com/articles/binary-data) retrieved from a communications medium.\nThis 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.\nIf the programming language's string implementation is not [8-bit clean](https://bliptext.com/articles/8-bit-clean), data corruption may ensue.\nC programmers draw a sharp distinction between a \"string\", aka a \"string of characters\", which by definition is always null terminated, vs. a \"array of characters\" which may be stored in the same array but is often not null terminated.\nUsing [C string handling](https://bliptext.com/articles/c-string-handling) functions on such an array of characters often seems to work, but later leads to [security problems](https://bliptext.com/articles/).\n\n# String processing algorithms\nThere are many [algorithms](https://bliptext.com/articles/algorithm) for processing strings, each with various trade-offs.\nCompeting algorithms can be [analyzed](https://bliptext.com/articles/analysis-of-algorithms) with respect to run time, storage requirements, and so forth.\nThe name **stringology** was coined in 1984 by computer scientist [Zvi Galil](https://bliptext.com/articles/zvi-galil) for the theory of algorithms and data structures used for string processing.\nSome categories of algorithms include:\nAdvanced string algorithms often employ complex mechanisms and data structures, among them [suffix trees](https://bliptext.com/articles/suffix-tree) and [finite-state machines](https://bliptext.com/articles/finite-state-machine).\n\n# Character string-oriented languages and utilities\nCharacter strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write.\nExamples include the following languages:\nMany [Unix](https://bliptext.com/articles/unix) utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms.\nFiles and finite streams may be viewed as strings.\nSome [APIs](https://bliptext.com/articles/application-programming-interface) like [Multimedia Control Interface](https://bliptext.com/articles/multimedia-control-interface), [embedded SQL](https://bliptext.com/articles/embedded-sql) or [printf](https://bliptext.com/articles/printf) use strings to hold commands that will be interpreted.\nMany [scripting programming languages](https://bliptext.com/articles/scripting-programming-language), including Perl, [Python](https://bliptext.com/articles/python-programming-language), Ruby, and Tcl employ [regular expressions](https://bliptext.com/articles/regular-expression) to facilitate text operations.\nPerl is particularly noted for its regular expression use, and many other languages and applications implement [Perl compatible regular expressions](https://bliptext.com/articles/perl-compatible-regular-expressions).\nSome languages such as Perl and Ruby support [string interpolation](https://bliptext.com/articles/string-interpolation), which permits arbitrary expressions to be evaluated and included in string literals.\n\n# Character string functions\n[String functions](https://bliptext.com/articles/string-function) are used to create strings or change the contents of a mutable string.\nThey also are used to query information about a string.\nThe set of functions and their names varies depending on the [computer programming language](https://bliptext.com/articles/programming-language).\nThe most basic example of a string function is the [string length](https://bliptext.com/articles/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.\nThis function is often named or.\nFor example, would return 11.\nAnother common function is [concatenation](https://bliptext.com/articles/concatenation), where a new string is created by appending two strings, often this is the + addition operator.\nSome [microprocessor](https://bliptext.com/articles/microprocessor)'s [instruction set architectures](https://bliptext.com/articles/instruction-set-architecture) contain direct support for string operations, such as block copy (e.g. In [intel x86m](https://bliptext.com/articles/intel-x86) ).\n\n# Formal theory\nLet Σ be a [finite set](https://bliptext.com/articles/finite-set) of distinct, unambiguous symbols (alternatively called characters), called the [alphabet](https://bliptext.com/articles/alphabet-formal-languages).\nA **string** (or **word** or **expression** ) over Σ is any finite [sequence](https://bliptext.com/articles/sequence) of symbols from Σ.\nFor example, if Σ = {0, 1}, then 01011 is a string over Σ.\nThe [length](https://bliptext.com/articles/length) of a string s is the number of symbols in s (the [length](https://bliptext.com/articles/length) of the sequence) and can be any [non-negative integer](https://bliptext.com/articles/non-negative-integer); it is often denoted as |s|.\nThe [empty string](https://bliptext.com/articles/empty-string) is the unique string over Σ of length 0, and is denoted ε or λ.\nThe set of all strings over Σ of length n is denoted Σn.\nFor example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}.\nWe have Σ0 = {ε} for every alphabet Σ.\nThe set of all strings over Σ of any length is the [Kleene closure](https://bliptext.com/articles/kleene-star) of Σ and is denoted Σ*.\nIn terms of Σn,\nFor example, if Σ = {0, 1}, then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}.\nAlthough the set Σ* itself is [countably infinite](https://bliptext.com/articles/countably-infinite), each element of Σ* is a string of finite length.\nA set of strings over Σ (i.e. any [subset](https://bliptext.com/articles/subset) of Σ*) is called a [formal language](https://bliptext.com/articles/formal-language) over Σ.\nFor 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 Σ.\n\n## Concatenation and substrings\n[Concatenation](https://bliptext.com/articles/concatenation) is an important [binary operation](https://bliptext.com/articles/binary-operation) on Σ*.\nFor 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.\nFor example, if Σ = {a, b, ..., z}, s = bear, and t = hug, then st = bearhug and ts = hugbear.\nString concatenation is an [associative](https://bliptext.com/articles/associative), but non-[commutative](https://bliptext.com/articles/commutative) operation.\nThe empty string ε serves as the [identity element](https://bliptext.com/articles/identity-element); for any string s, εs = sε = s.\nTherefore, the set Σ* and the concatenation operation form a [monoid](https://bliptext.com/articles/monoid), the free [monoid](https://bliptext.com/articles/monoid) generated by Σ.\nIn addition, the length function defines a [monoid homomorphism](https://bliptext.com/articles/monoid-homomorphism) from Σ* to the non-negative integers (that is, a function, such that ).\nA string s is said to be a [substring](https://bliptext.com/articles/substring) or factor of t if there exist (possibly empty) strings u and v such that t = usv.\nThe [relation](https://bliptext.com/articles/binary-relation) \"is a substring of\" defines a [partial order](https://bliptext.com/articles/partial-order) on Σ*, the [least element](https://bliptext.com/articles/least-element) of which is the empty string.\n\n## Prefixes and suffixes\nA string s is said to be a [prefix](https://bliptext.com/articles/substring) of t if there exists a string u such that t = su.\nIf u is nonempty, s is said to be a proper prefix of t.\nSymmetrically, a string s is said to be a [suffix](https://bliptext.com/articles/substring) of t if there exists a string u such that t = us.\nIf u is nonempty, s is said to be a proper suffix of t.\nSuffixes and prefixes are substrings of t.\nBoth the relations \"is a prefix of\" and \"is a suffix of\" are [prefix orders](https://bliptext.com/articles/prefix-order).\n\n## Reversal\nThe reverse of a string is a string with the same symbols but in reverse order.\nFor example, if s = abc (where a, b, and c are symbols of the alphabet), then the reverse of s is cba.\nA string that is the reverse of itself (e.g., s = madam) is called a [palindrome](https://bliptext.com/articles/palindrome), which also includes the empty string and all strings of length 1.\n\n## Rotations\nA string s = uv is said to be a rotation of t if t = vu.\nFor example, if Σ = {0, 1} the string 0011001 is a rotation of 0100110, where u = 00110 and v = 01.\nAs another example, the string abc has three different rotations, viz.\nabc itself (with u=abc, v=ε), bca (with u=bc, v=a), and cab (with u=c, v=ab).\n\n## Lexicographical ordering\nIt is often useful to define an [ordering](https://bliptext.com/articles/order-theory) on a set of strings.\nIf the alphabet Σ has a [total order](https://bliptext.com/articles/total-order) (cf. [alphabetical order](https://bliptext.com/articles/alphabetical-order)) one can define a [total order](https://bliptext.com/articles/total-order) on Σ* called [lexicographical order](https://bliptext.com/articles/lexicographical-order).\nThe lexicographical order is [total](https://bliptext.com/articles/total-order) if the alphabetical order is, but is not [well-founded](https://bliptext.com/articles/well-founded) for any nontrivial alphabet, even if the alphabetical order is.\nFor example, if Σ = {0, 1} 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 ... With respect to this ordering, e.g. the infinite set { 1, 01, 001, 0001, 00001, 000001, ... } has no minimal element.\nSee [Shortlex](https://bliptext.com/articles/shortlex) for an alternative string ordering that preserves well-foundedness.\nFor 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 ...\n\n## String operations\nA number of additional operations on strings commonly occur in the formal theory.\nThese are given in the article on [string operations](https://bliptext.com/articles/string-operations).\n\n## Topology\nStrings admit the following interpretation as nodes on a graph, where k is the number of symbols in Σ:\nThe 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](https://bliptext.com/articles/limit-topology), viewing the set of infinite strings as the [inverse limit](https://bliptext.com/articles/inverse-limit) of the sets of finite strings.\nThis is the construction used for the p-adic numbers and some constructions of the [Cantor set](https://bliptext.com/articles/cantor-set), and yields the same topology.\n[Isomorphisms](https://bliptext.com/articles/isomorphism) between string representations of topologies can be found by normalizing according to the [lexicographically minimal string rotation](https://bliptext.com/articles/lexicographically-minimal-string-rotation).\n# [(Hyper)cube of binary strings of length 3 | upload.wikimedia.org/wikipedia/commons/b/b4/Hamming///distance///3///bit///binary.svg]","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T17:23:32.597Z","updated_at":"2025-01-25T17:23:32.597Z","search_vector":"'comput':2 'scienc':3 'string':1","search_content":" \n \n\n# \nIn [computer programming](https://bliptext.com/articles/computer-programming), a **string** is traditionally a [sequence](https://bliptext.com/articles/sequence) of [characters](https://bliptext.com/articles/character-computing), either as a [literal constant](https://bliptext.com/articles/literal-computer-programming) or as some kind of [variable](https://bliptext.com/articles/variable-computer-science).\nThe latter may allow its elements to be [mutated](https://bliptext.com/articles/immutable-object) and the length changed, or it may be fixed (after creation).\nA string is generally considered as a [data type](https://bliptext.com/articles/data-type) and is often implemented as an [array data structure](https://bliptext.com/articles/array-data-structure) of [bytes](https://bliptext.com/articles/byte) (or [words](https://bliptext.com/articles/word-computer-architecture)) that stores a sequence of elements, typically characters, using some [character encoding](https://bliptext.com/articles/character-encoding).\nString may also denote more general [arrays](https://bliptext.com/articles/array-data-type) or other sequence (or [list](https://bliptext.com/articles/list-abstract-data-type)) data types and structures.\nDepending on the programming language and precise data type used, a [variable](https://bliptext.com/articles/variable-programming) declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employ [dynamic allocation](https://bliptext.com/articles/dynamic-allocation) to allow it to hold a [variable](https://bliptext.com/articles/variable-programming) number of elements.\nWhen a string appears literally in [source code](https://bliptext.com/articles/source-code), it is known as a [string literal](https://bliptext.com/articles/string-literal) or an anonymous string.\nIn [formal languages](https://bliptext.com/articles/formal-language), which are used in [mathematical logic](https://bliptext.com/articles/mathematical-logic) and [theoretical computer science](https://bliptext.com/articles/theoretical-computer-science), a string is a finite sequence of [symbols](https://bliptext.com/articles/symbol-formal) that are chosen from a [set](https://bliptext.com/articles/set-mathematics) called an [alphabet](https://bliptext.com/articles/alphabet-computer-science).\n# [Strings are typically made up of characters, and are often used to store human-readable data, such as words or sentences. | upload.wikimedia.org/wikipedia/commons/6/6b/String///example.png]\n\n# Purpose\nA primary purpose of strings is to store human-readable text, like words and sentences.\nStrings are used to communicate information from a computer program to the user of the program.\nA program may also accept string input from its user.\nFurther, strings may store data expressed as characters yet not intended for human reading.\nExample strings and their purposes:\nThe term string may also designate a sequence of data or computer records other than characters — like a \"string of [bits](https://bliptext.com/articles/bit)\" — but when used without qualification it refers to strings of characters.\n\n# History\nUse of the word \"string\" to mean any items arranged in a line, series or succession dates back centuries.\nIn 19th-Century typesetting, [compositors](https://bliptext.com/articles/compositor-typesetting) used the term \"string\" to denote a length of type printed on paper; the string would be measured to determine the compositor's pay.\nUse of the word \"string\" to mean \"a sequence of symbols or linguistic elements in a definite order\" emerged from mathematics, [symbolic logic](https://bliptext.com/articles/symbolic-logic), and [linguistic theory](https://bliptext.com/articles/linguistic-theory) to speak about the [formal](https://bliptext.com/articles/formal-system) behavior of symbolic systems, setting aside the symbols' meaning.\nFor example, logician [C. I. Lewis](https://bliptext.com/articles/c-i-lewis) wrote in 1918:\nA 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.\nThat a system should consist of 'marks' instead of sounds or odours is immaterial.\nAccording to [Jean E. Sammet](https://bliptext.com/articles/jean-e-sammet), \"the first realistic string handling and pattern matching language\" for computers was [COMIT](https://bliptext.com/articles/comit) in the 1950s, followed by the [SNOBOL](https://bliptext.com/articles/snobol) language of the early 1960s.\n\n# String datatypes\nA **string datatype** is a datatype modeled on the idea of a formal string.\nStrings are such an important and useful datatype that they are implemented in nearly every [programming language](https://bliptext.com/articles/programming-language).\nIn some languages they are available as [primitive types](https://bliptext.com/articles/primitive-type) and in others as [composite types](https://bliptext.com/articles/composite-type).\nThe [syntax](https://bliptext.com/articles/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.\n\n## String length\nAlthough formal strings can have an arbitrary finite length, the length of strings in real languages is often constrained to an artificial maximum.\nIn general, there are two types of string datatypes: fixed-length strings, which have a fixed maximum length to be determined at [compile time](https://bliptext.com/articles/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](https://bliptext.com/articles/memory-management)).\nMost strings in modern [programming languages](https://bliptext.com/articles/programming-languages) are variable-length strings.\nOf course, even variable-length strings are limited in length – by the size of available [computer memory](https://bliptext.com/articles/computer-memory).\nThe 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.\nSee also \"[Null-terminated](https://bliptext.com/articles/)\" below.\n\n## Character encoding\nString 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.\nThese character sets were typically based on [ASCII](https://bliptext.com/articles/ascii) or [EBCDIC](https://bliptext.com/articles/ebcdic).\nIf text in one encoding was displayed on a system using a different encoding, text was often [mangled](https://bliptext.com/articles/mojibake), though often somewhat readable and some computer users learned to read the [mangled](https://bliptext.com/articles/mojibake) text.\n[Logographic](https://bliptext.com/articles/logograph) languages such as [Chinese](https://bliptext.com/articles/chinese-language), [Japanese](https://bliptext.com/articles/japanese-language), and [Korean](https://bliptext.com/articles/korean-language) (known collectively as [CJK](https://bliptext.com/articles/cjk-characters)) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation.\nThe normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK [ideographs](https://bliptext.com/articles/ideographs).\nUse 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.\nSome encodings such as the [EUC](https://bliptext.com/articles/extended-unix-code) 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.\nOther encodings such as [ISO-2022](https://bliptext.com/articles/iso-2022) and [Shift-JIS](https://bliptext.com/articles/shift-jis) do not make such guarantees, making matching on byte codes unsafe.\nThese 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.\n[Unicode](https://bliptext.com/articles/unicode) has simplified the picture somewhat.\nMost programming languages now have a datatype for Unicode strings.\nUnicode's preferred byte stream format [UTF-8](https://bliptext.com/articles/utf-8) is designed not to have the problems described above for older multibyte encodings.\nUTF-8, UTF-16 and [UTF-32](https://bliptext.com/articles/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](https://bliptext.com/articles/utf-32) does make code points fixed-sized, but these are not \"characters\" due to composing codes).\n\n## Implementations\nSome languages, such as [C++](https://bliptext.com/articles/c), [Perl](https://bliptext.com/articles/perl) and [Ruby](https://bliptext.com/articles/ruby-programming-language), normally allow the contents of a string to be changed after it has been created; these are termed mutable strings.\nIn other languages, such as [Java](https://bliptext.com/articles/java-programming-language), [Java](https://bliptext.com/articles/java-programming-language)Script, [Lua](https://bliptext.com/articles/lua-programming-language), [Python](https://bliptext.com/articles/python-programming-language), and [Go](https://bliptext.com/articles/go-programming-language), the value is fixed and a new string must be created if any alteration is to be made; these are termed immutable strings.\nSome of these languages with immutable strings also provide another type that is mutable, such as Java and [.NET](https://bliptext.com/articles/net-framework)'s, the thread-safe Java , and the [Cocoa](https://bliptext.com/articles/cocoa-api).\nThere are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completely [thread-safe](https://bliptext.com/articles/thread-safety).\nStrings are typically implemented as [arrays](https://bliptext.com/articles/array-data-type) 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.\nA few languages such as [Haskell](https://bliptext.com/articles/haskell-programming-language) implement them as [linked lists](https://bliptext.com/articles/linked-list) instead.\nA lot of high-level languages provide strings as a primitive data type, such as [[Java](https://bliptext.com/articles/java-programming-language)Script](https://bliptext.com/articles/javascript) and [PHP](https://bliptext.com/articles/php), while most others provide them as a composite data type, some with special language support in writing literals, for example, [Java](https://bliptext.com/articles/java-programming-language) and [C#](https://bliptext.com/articles/c-sharp-programming-language).\nSome languages, such as [C](https://bliptext.com/articles/c-programming-language), [Prolog](https://bliptext.com/articles/prolog) and [Erlang](https://bliptext.com/articles/erlang-programming-language), avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes.\nEven in programming languages having a dedicated string type, string can usually be iterated as a sequence character codes, like lists of integers or other values.\n\n## Representations\nRepresentations of strings depend heavily on the choice of character repertoire and the method of character encoding.\nOlder string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the [ISO 8859](https://bliptext.com/articles/iso-8859) series.\nModern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16.\nThe term byte string usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such.\nByte 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.\nMost string implementations are very similar to variable-length [arrays](https://bliptext.com/articles/array-data-type) with the entries storing the [character codes](https://bliptext.com/articles/character-code) of corresponding characters.\nThe principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array.\nThis happens for example with UTF-8, where single codes ([UCS](https://bliptext.com/articles/universal-character-set) code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes.\nIn these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use).\n[UTF-32](https://bliptext.com/articles/utf-32) avoids the first part of the problem.\n\n### Null-terminated\nThe length of a string can be stored implicitly by using a special terminating character; often this is the [null character](https://bliptext.com/articles/null-character) (NUL), which has all bits zero, a convention used and perpetuated by the popular [C programming language](https://bliptext.com/articles/c-programming-language).\nHence, this representation is commonly referred to as a **C string**.\nThis representation of an n-character string takes n + 1 space (1 for the terminator), and is thus an [implicit data structure](https://bliptext.com/articles/implicit-data-structure).\nIn terminated strings, the terminating code is not an allowable character in any string.\nStrings with length field do not have this limitation and can also store arbitrary [binary data](https://bliptext.com/articles/binary-data).\nAn example of a null-terminated string stored in a 10-byte [buffer](https://bliptext.com/articles/buffer-computer-science), along with its [ASCII](https://bliptext.com/articles/ascii) (or more modern [UTF-8](https://bliptext.com/articles/utf-8)) representation as 8-bit [hexadecimal numbers](https://bliptext.com/articles/hexadecimal-number) is:\nThe length of the string in the above example, \" \", is 5 characters, but it occupies 6 bytes.\nCharacters after the terminator do not form part of the representation; they may be either part of other data or just garbage.\n(Strings of this form are sometimes called ASCIZ strings, after the original [assembly language](https://bliptext.com/articles/assembly-language) directive used to declare them.)\n\n### Byte- and bit-terminated\nUsing 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.\nwas used by many assembler systems, used by [CDC](https://bliptext.com/articles/control-data-corporation) systems (this character had a value of zero), and the [ZX80](https://bliptext.com/articles/zx80) used since this was the string delimiter in its BASIC language.\nSomewhat similar, \"data processing\" machines like the [IBM 1401](https://bliptext.com/articles/ibm-1401) used a special [word mark](https://bliptext.com/articles/word-mark-computer-hardware) bit to delimit strings at the left, where the operation would start at the right.\nThis bit had to be clear in all other parts of the string.\nThis 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.\nEarly 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.\nIt must be reset to 0 prior to output.\n\n### Length-prefixed\nThe length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value.\nThis convention is used in many [Pascal](https://bliptext.com/articles/pascal-programming-language) dialects; as a consequence, some people call such a string a **[Pascal](https://bliptext.com/articles/pascal-programming-language) string** or **P-string**.\nStoring the string length as byte limits the maximum string length to 255.\nTo avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit [words](https://bliptext.com/articles/word-data-type) to store the string length.\nWhen the length field covers the [address space](https://bliptext.com/articles/address-space), strings are limited only by the [available memory](https://bliptext.com/articles/dynamic-memory-allocation).\nIf the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an [implicit data structure](https://bliptext.com/articles/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.).\nIf the length is not bounded, encoding a length n takes log(n) space (see [fixed-length code](https://bliptext.com/articles/fixed-length-code)), so length-prefixed strings are a [succinct data structure](https://bliptext.com/articles/succinct-data-structure), encoding a string of length n in log(n) + n space.\nIn 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.\nHere is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:\n\n### Strings as records\nMany languages, including object-oriented ones, implement strings as [records](https://bliptext.com/articles/record-computer-science) with an internal structure like:\nHowever, since the implementation is usually [hidden](https://bliptext.com/articles/information-hiding), the string must be accessed and modified through member functions.\nis a pointer to a dynamically allocated memory area, which might be expanded as needed.\nSee also [string (C++)](https://bliptext.com/articles/string-c).\n\n### Other representations\nBoth character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by [C string](https://bliptext.com/articles/c-string-handling) library functions: Strings using a length code are limited to the maximum value of the length code.\nBoth of these limitations can be overcome by clever programming.\nIt 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.\nIt is also possible to optimize the string represented using techniques from [run length encoding](https://bliptext.com/articles/run-length-encoding) (replacing repeated characters by the character value and a length) and [Hamming encoding](https://bliptext.com/articles/hamming-coding).\nWhile these representations are common, others are possible.\nUsing [ropes](https://bliptext.com/articles/rope-data-structure) makes certain string operations, such as insertions, deletions, and concatenations more efficient.\nThe core data structure in a [text editor](https://bliptext.com/articles/text-editor) is the one that manages the string (sequence of characters) that represents the current state of the file being edited.\nWhile 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](https://bliptext.com/articles/gap-buffer), a [linked list](https://bliptext.com/articles/linked-list) of lines, a [piece table](https://bliptext.com/articles/piece-table), or a [rope](https://bliptext.com/articles/rope-data-structure)—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.\n\n## Security concerns\nThe differing memory layout and storage requirements of strings can affect the security of the program accessing the string data.\nString representations requiring a terminating character are commonly susceptible to [buffer overflow](https://bliptext.com/articles/buffer-overflow) problems if the terminating character is not present, caused by a coding error or an [attacker](https://bliptext.com/articles/hacker-computer-security) deliberately altering the data.\nString representations adopting a separate length field are also susceptible if the length can be manipulated.\nIn such cases, program code accessing the string data requires [bounds checking](https://bliptext.com/articles/bounds-checking) to ensure that it does not inadvertently access or change data outside of the string memory limits.\nString data is frequently obtained from user input to a program.\nAs such, it is the responsibility of the program to validate the string to ensure that it represents the expected format.\nPerforming [limited or no validation](https://bliptext.com/articles/improper-input-validation) of user input can cause a program to be vulnerable to [code injection](https://bliptext.com/articles/code-injection) attacks.\n\n# Literal strings\nSometimes, strings need to be embedded inside a text file that is both human-readable and intended for consumption by a machine.\nThis is needed in, for example, source code of programming languages, or in configuration files.\nIn 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.\nStoring the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone.\nTwo common representations are:\n\n# Non-text strings\nWhile character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data.\nA [bit string](https://bliptext.com/articles/bit-string) or [byte string](https://bliptext.com/articles/byte-string), for example, may be used to represent non-textual [binary data](https://bliptext.com/articles/binary-data) retrieved from a communications medium.\nThis 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.\nIf the programming language's string implementation is not [8-bit clean](https://bliptext.com/articles/8-bit-clean), data corruption may ensue.\nC programmers draw a sharp distinction between a \"string\", aka a \"string of characters\", which by definition is always null terminated, vs. a \"array of characters\" which may be stored in the same array but is often not null terminated.\nUsing [C string handling](https://bliptext.com/articles/c-string-handling) functions on such an array of characters often seems to work, but later leads to [security problems](https://bliptext.com/articles/).\n\n# String processing algorithms\nThere are many [algorithms](https://bliptext.com/articles/algorithm) for processing strings, each with various trade-offs.\nCompeting algorithms can be [analyzed](https://bliptext.com/articles/analysis-of-algorithms) with respect to run time, storage requirements, and so forth.\nThe name **stringology** was coined in 1984 by computer scientist [Zvi Galil](https://bliptext.com/articles/zvi-galil) for the theory of algorithms and data structures used for string processing.\nSome categories of algorithms include:\nAdvanced string algorithms often employ complex mechanisms and data structures, among them [suffix trees](https://bliptext.com/articles/suffix-tree) and [finite-state machines](https://bliptext.com/articles/finite-state-machine).\n\n# Character string-oriented languages and utilities\nCharacter strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write.\nExamples include the following languages:\nMany [Unix](https://bliptext.com/articles/unix) utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms.\nFiles and finite streams may be viewed as strings.\nSome [APIs](https://bliptext.com/articles/application-programming-interface) like [Multimedia Control Interface](https://bliptext.com/articles/multimedia-control-interface), [embedded SQL](https://bliptext.com/articles/embedded-sql) or [printf](https://bliptext.com/articles/printf) use strings to hold commands that will be interpreted.\nMany [scripting programming languages](https://bliptext.com/articles/scripting-programming-language), including Perl, [Python](https://bliptext.com/articles/python-programming-language), Ruby, and Tcl employ [regular expressions](https://bliptext.com/articles/regular-expression) to facilitate text operations.\nPerl is particularly noted for its regular expression use, and many other languages and applications implement [Perl compatible regular expressions](https://bliptext.com/articles/perl-compatible-regular-expressions).\nSome languages such as Perl and Ruby support [string interpolation](https://bliptext.com/articles/string-interpolation), which permits arbitrary expressions to be evaluated and included in string literals.\n\n# Character string functions\n[String functions](https://bliptext.com/articles/string-function) are used to create strings or change the contents of a mutable string.\nThey also are used to query information about a string.\nThe set of functions and their names varies depending on the [computer programming language](https://bliptext.com/articles/programming-language).\nThe most basic example of a string function is the [string length](https://bliptext.com/articles/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.\nThis function is often named or.\nFor example, would return 11.\nAnother common function is [concatenation](https://bliptext.com/articles/concatenation), where a new string is created by appending two strings, often this is the + addition operator.\nSome [microprocessor](https://bliptext.com/articles/microprocessor)'s [instruction set architectures](https://bliptext.com/articles/instruction-set-architecture) contain direct support for string operations, such as block copy (e.g. In [intel x86m](https://bliptext.com/articles/intel-x86) ).\n\n# Formal theory\nLet Σ be a [finite set](https://bliptext.com/articles/finite-set) of distinct, unambiguous symbols (alternatively called characters), called the [alphabet](https://bliptext.com/articles/alphabet-formal-languages).\nA **string** (or **word** or **expression** ) over Σ is any finite [sequence](https://bliptext.com/articles/sequence) of symbols from Σ.\nFor example, if Σ = {0, 1}, then 01011 is a string over Σ.\nThe [length](https://bliptext.com/articles/length) of a string s is the number of symbols in s (the [length](https://bliptext.com/articles/length) of the sequence) and can be any [non-negative integer](https://bliptext.com/articles/non-negative-integer); it is often denoted as |s|.\nThe [empty string](https://bliptext.com/articles/empty-string) is the unique string over Σ of length 0, and is denoted ε or λ.\nThe set of all strings over Σ of length n is denoted Σn.\nFor example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}.\nWe have Σ0 = {ε} for every alphabet Σ.\nThe set of all strings over Σ of any length is the [Kleene closure](https://bliptext.com/articles/kleene-star) of Σ and is denoted Σ*.\nIn terms of Σn,\nFor example, if Σ = {0, 1}, then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}.\nAlthough the set Σ* itself is [countably infinite](https://bliptext.com/articles/countably-infinite), each element of Σ* is a string of finite length.\nA set of strings over Σ (i.e. any [subset](https://bliptext.com/articles/subset) of Σ*) is called a [formal language](https://bliptext.com/articles/formal-language) over Σ.\nFor 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 Σ.\n\n## Concatenation and substrings\n[Concatenation](https://bliptext.com/articles/concatenation) is an important [binary operation](https://bliptext.com/articles/binary-operation) on Σ*.\nFor 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.\nFor example, if Σ = {a, b, ..., z}, s = bear, and t = hug, then st = bearhug and ts = hugbear.\nString concatenation is an [associative](https://bliptext.com/articles/associative), but non-[commutative](https://bliptext.com/articles/commutative) operation.\nThe empty string ε serves as the [identity element](https://bliptext.com/articles/identity-element); for any string s, εs = sε = s.\nTherefore, the set Σ* and the concatenation operation form a [monoid](https://bliptext.com/articles/monoid), the free [monoid](https://bliptext.com/articles/monoid) generated by Σ.\nIn addition, the length function defines a [monoid homomorphism](https://bliptext.com/articles/monoid-homomorphism) from Σ* to the non-negative integers (that is, a function, such that ).\nA string s is said to be a [substring](https://bliptext.com/articles/substring) or factor of t if there exist (possibly empty) strings u and v such that t = usv.\nThe [relation](https://bliptext.com/articles/binary-relation) \"is a substring of\" defines a [partial order](https://bliptext.com/articles/partial-order) on Σ*, the [least element](https://bliptext.com/articles/least-element) of which is the empty string.\n\n## Prefixes and suffixes\nA string s is said to be a [prefix](https://bliptext.com/articles/substring) of t if there exists a string u such that t = su.\nIf u is nonempty, s is said to be a proper prefix of t.\nSymmetrically, a string s is said to be a [suffix](https://bliptext.com/articles/substring) of t if there exists a string u such that t = us.\nIf u is nonempty, s is said to be a proper suffix of t.\nSuffixes and prefixes are substrings of t.\nBoth the relations \"is a prefix of\" and \"is a suffix of\" are [prefix orders](https://bliptext.com/articles/prefix-order).\n\n## Reversal\nThe reverse of a string is a string with the same symbols but in reverse order.\nFor example, if s = abc (where a, b, and c are symbols of the alphabet), then the reverse of s is cba.\nA string that is the reverse of itself (e.g., s = madam) is called a [palindrome](https://bliptext.com/articles/palindrome), which also includes the empty string and all strings of length 1.\n\n## Rotations\nA string s = uv is said to be a rotation of t if t = vu.\nFor example, if Σ = {0, 1} the string 0011001 is a rotation of 0100110, where u = 00110 and v = 01.\nAs another example, the string abc has three different rotations, viz.\nabc itself (with u=abc, v=ε), bca (with u=bc, v=a), and cab (with u=c, v=ab).\n\n## Lexicographical ordering\nIt is often useful to define an [ordering](https://bliptext.com/articles/order-theory) on a set of strings.\nIf the alphabet Σ has a [total order](https://bliptext.com/articles/total-order) (cf. [alphabetical order](https://bliptext.com/articles/alphabetical-order)) one can define a [total order](https://bliptext.com/articles/total-order) on Σ* called [lexicographical order](https://bliptext.com/articles/lexicographical-order).\nThe lexicographical order is [total](https://bliptext.com/articles/total-order) if the alphabetical order is, but is not [well-founded](https://bliptext.com/articles/well-founded) for any nontrivial alphabet, even if the alphabetical order is.\nFor example, if Σ = {0, 1} 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 ... With respect to this ordering, e.g. the infinite set { 1, 01, 001, 0001, 00001, 000001, ... } has no minimal element.\nSee [Shortlex](https://bliptext.com/articles/shortlex) for an alternative string ordering that preserves well-foundedness.\nFor 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 ...\n\n## String operations\nA number of additional operations on strings commonly occur in the formal theory.\nThese are given in the article on [string operations](https://bliptext.com/articles/string-operations).\n\n## Topology\nStrings admit the following interpretation as nodes on a graph, where k is the number of symbols in Σ:\nThe 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](https://bliptext.com/articles/limit-topology), viewing the set of infinite strings as the [inverse limit](https://bliptext.com/articles/inverse-limit) of the sets of finite strings.\nThis is the construction used for the p-adic numbers and some constructions of the [Cantor set](https://bliptext.com/articles/cantor-set), and yields the same topology.\n[Isomorphisms](https://bliptext.com/articles/isomorphism) between string representations of topologies can be found by normalizing according to the [lexicographically minimal string rotation](https://bliptext.com/articles/lexicographically-minimal-string-rotation).\n# [(Hyper)cube of binary strings of length 3 | upload.wikimedia.org/wikipedia/commons/b/b4/Hamming///distance///3///bit///binary.svg]","revisionCount":0},"hasMore":false,"nextCursor":null}