Incomputer programming, astring is traditionally asequence ofcharacters, either as aliteral constant or as some kind ofvariable. The latter may allow its elements to bemutated and the length changed, or it may be fixed (after creation). A string is generally considered as adata type and is often implemented as anarray data structure ofbytes (orwords) that stores a sequence of elements, typically characters, using somecharacter encoding.String may also denote more generalarrays or other sequence (orlist) data types and structures.
Depending on the programming language and precise data type used, avariable declared to be a string may either cause storage in memory to be statically allocated for a predetermined maximum length or employdynamic allocation to allow it to hold a variable number of elements.
When a string appears literally insource code, it is known as astring literal or an anonymous string.[1]
Informal languages, which are used inmathematical logic andtheoretical computer science, a string is a finite sequence ofsymbols that are chosen from aset called analphabet.
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.[2] 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:
file upload complete" is a string that software shows toend users. In the program'ssource code, this message would likely appear as astring literal.I got a new job today" as a status update on asocial media service. Instead of a string literal, the software would likely store this string in adatabase.AGATGCCGT" representing nucleic acid sequences ofDNA.[3]?action=edit" as a URLquery 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 — like a "string ofbits" — but when used without qualification it refers to strings of characters.[4]
Use of the word "string" to mean any items arranged in a line, series or succession dates back centuries.[5][6] 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.[7][4][8]
Use of the word "string" to mean "a sequence of symbols or linguistic elements in a definite order" emerged from mathematics,symbolic logic, andlinguistic theory to speak about theformal behavior of symbolic systems, setting aside the symbols' meaning.[4]
For example, logicianC. I. Lewis wrote in 1918:[9]
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.
According toJean E. Sammet, "the first realistic string handling and pattern matching language" for computers wasCOMIT in the 1950s, followed by theSNOBOL language of the early 1960s.[10]
Astring 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 everyprogramming language. In some languages they are available asprimitive types and in others ascomposite types. Thesyntax 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 aliteral orstring literal.
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 atcompile time and which use the same amount of memory whether this maximum is needed or not, andvariable-length strings, whose length is not arbitrarily fixed and which can use varying amounts of memory depending on the actual requirements at run time (seeMemory management). Most strings in modernprogramming languages are variable-length strings. Of course, even variable-length strings are limited in length by the amount of available memory. The string length can be stored as a separate integer (which may put another artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero such as in C programming language. See also "Null-terminated" below.
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 onASCII orEBCDIC. If text in one encoding was displayed on a system using a different encoding, text was oftenmangled, though often somewhat readable and some computer users learned to read the mangled text.
Logographic languages such asChinese,Japanese, andKorean (known collectively asCJK) 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 CJKideographs. 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 theEUC 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 asISO-2022 andShift-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 formatUTF-8 is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 andUTF-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 makecode points fixed-sized, but these are not "characters" due to composing codes).
Some languages, such asC++,Perl andRuby, normally allow the contents of a string to be changed after it has been created; these are termedmutable strings. In other languages, such asJava,JavaScript,Lua,Python, andGo, the value is fixed and a new string must be created if any alteration is to be made; these are termedimmutable strings. Some of these languages with immutable strings also provide another type that is mutable, such as Java and.NET'sStringBuilder, the thread-safe JavaStringBuffer, and theCocoaNSMutableString. There are both advantages and disadvantages to immutability: although immutable strings may require inefficiently creating many copies, they are simpler and completelythread-safe.
Strings are typically implemented asarrays 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 asHaskell implement them aslinked lists instead.
A lot of high-level languages provide strings as a primitive data type, such asJavaScript andPHP, while most others provide them as a composite data type, some with special language support in writing literals, for example,Java andC#.
Some languages, such asC,Prolog andErlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes. Even in programming languages having a dedicated string type, string can usually be iterated as a sequence character codes, like lists of integers or other values.
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 theISO 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 termbyte 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-lengtharrays with the entries storing thecharacter 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.
The length of a string can be stored implicitly by using a special terminating character; often this is thenull character (NUL), which has all bits zero, a convention used and perpetuated by the popularC programming language.[11] Hence, this representation is commonly referred to as aC string. This representation of ann-character string takesn + 1 space (1 for the terminator), and is thus animplicit data structure.
In terminated strings, the terminating code is not an allowable character in any string. Strings withlength field do not have this limitation and can also store arbitrarybinary data.
An example of anull-terminated string stored in a 10-bytebuffer, along with itsASCII (or more modernUTF-8) representation as 8-bithexadecimal numbers is:
F | R | A | N | K | NUL | k | e | f | w |
| 4616 | 5216 | 4116 | 4E16 | 4B16 | 0016 | 6B16 | 6516 | 6616 | 7716 |
The length of the string in the above example, "FRANK", is 5 characters, but it occupies 6 bytes. Characters after the terminator do not form part of the representation; they may be either part of other data or just garbage. (Strings of this form are sometimes calledASCIZ strings, after the originalassembly language directive used to declare them.)
Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character.$ was used by many assembler systems,: used byCDC systems (this character had a value of zero), and theZX80 used"[12] since this was the string delimiter in its BASIC language.
Somewhat similar, "data processing" machines like theIBM 1401 used a specialword 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.[13]
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 manyPascal dialects; as a consequence, some people call such a string aPascal string orP-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-bitwords to store the string length. When thelength field covers theaddress space, strings are limited only by theavailable memory.
If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to animplicit data structure, takingn +k space, wherek 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 lengthn takes log(n) space (seefixed-length code), so length-prefixed strings are asuccinct data structure, encoding a string of lengthn 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.
Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:
| length | F | R | A | N | K | k | e | f | w |
| 0516 | 4616 | 5216 | 4116 | 4E16 | 4B16 | 6B16 | 6516 | 6616 | 7716 |
Many languages, including object-oriented ones, implement strings asrecords with an internal structure like:
classstring{size_tlength;char*text;};
However, since the implementation is usuallyhidden, the string must be accessed and modified through member functions.text is a pointer to a dynamically allocated memory area, which might be expanded as needed. See alsostring (C++).
Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly byC 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 fromrun length encoding (replacing repeated characters by the character value and a length) andHamming encoding[clarification needed].
While these representations are common, others are possible. Usingropes makes certain string operations, such as insertions, deletions, and concatenations more efficient.
The core data structure in atext 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—agap buffer, alinked list of lines, apiece table, or arope—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.[14]
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 tobuffer overflow problems if the terminating character is not present, caused by a coding error or anattacker 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 requiresbounds 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. Performinglimited or no validation of user input can cause a program to be vulnerable tocode injection attacks.
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:
"str" or ASCII 0x27 single quote'str'), 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 sequences are often available, usually prefixed with thebackslash character (ASCII 0x5C).While character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data. Abit string orbyte string, for example, may be used to represent non-textualbinary 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 not8-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 "array of characters" which may be stored in the same array but is often not null terminated.UsingC string handling functions on such an array of characters often seems to work, but later leads tosecurity problems.[15][16][17]
There are manyalgorithms for processing strings, each with various trade-offs. Competing algorithms can beanalyzed with respect to run time, storage requirements, and so forth. The namestringology was coined in 1984 by computer scientistZvi Galil for the theory of algorithms and data structures used for string processing.[18][19][20]
Some categories of algorithms include:
Advanced string algorithms often employ complex mechanisms and data structures, among themsuffix trees andfinite-state machines.
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:
ManyUnix 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.
SomeAPIs likeMultimedia Control Interface,embedded SQL orprintf use strings to hold commands that will be interpreted.
Manyscripting programming languages, including Perl,Python, Ruby, and Tcl employregular expressions to facilitate text operations. Perl is particularly noted for its regular expression use,[21] and many other languages and applications implementPerl compatible regular expressions.
Some languages such as Perl and Ruby supportstring interpolation, which permits arbitrary expressions to be evaluated and included in string literals.
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 thecomputer programming language.
The most basic example of a string function is thestring 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 namedlength orlen. For example,length("hello world") would return 11. Another common function isconcatenation, where a new string is created by appending two strings, often this is the + addition operator.
Somemicroprocessor'sinstruction set architectures contain direct support for string operations, such as block copy (e.g. Inintel x86mREPNZ MOVSB).[22]
Let Σ be afinite set of distinct, unambiguous symbols (alternatively called characters), called thealphabet. Astring (orword[23] orexpression[24]) over Σ is any finitesequence of symbols from Σ.[25] For example, if Σ = {0, 1}, then01011 is a string over Σ.
Thelength of a strings is the number of symbols ins (the length of the sequence) and can be anynon-negative integer; it is often denoted as |s|. Theempty string is the unique string over Σ of length 0, and is denotedε orλ.[25][26]
The set of all strings over Σ of lengthn is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. We have Σ0 = {ε} for every alphabet Σ.
The set of all strings over Σ of any length is theKleene closure of Σ and is denoted Σ*. In terms of Σn,
For example, if Σ = {0, 1}, then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Although the set Σ* itself iscountably infinite, each element of Σ* is a string of finite length.
A set of strings over Σ (i.e. anysubset of Σ*) is called aformal 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 is an importantbinary operation on Σ*. For any two stringss andt in Σ*, their concatenation is defined as the sequence of symbols ins followed by the sequence of characters int, and is denotedst. For example, if Σ = {a, b, ..., z},s = bear, andt = hug, thenst = bearhug andts = hugbear.
String concatenation is anassociative, but non-commutative operation. The empty string ε serves as theidentity element; for any strings, εs =sε =s. Therefore, the set Σ* and the concatenation operation form amonoid, thefree monoid generated by Σ. In addition, the length function defines amonoid homomorphism from Σ* to the non-negative integers (that is, a function, such that).
A strings is said to be asubstring orfactor oft if there exist (possibly empty) stringsu andv such thatt =usv. Therelation "is a substring of" defines apartial order on Σ*, theleast element of which is the empty string.
A strings is said to be aprefix oft if there exists a stringu such thatt =su. Ifu is nonempty,s is said to be aproper prefix oft. Symmetrically, a strings is said to be asuffix oft if there exists a stringu such thatt =us. Ifu is nonempty,s is said to be aproper suffix oft. Suffixes and prefixes are substrings oft. Both the relations "is a prefix of" and "is a suffix of" areprefix orders.
The reverse of a string is a string with the same symbols but in reverse order. For example, ifs = abc (where a, b, and c are symbols of the alphabet), then the reverse ofs is cba. A string that is the reverse of itself (e.g.,s = madam) is called apalindrome, which also includes the empty string and all strings of length 1.
A strings =uv is said to be a rotation oft ift =vu. For example, if Σ = {0, 1} the string 0011001 is a rotation of 0100110, whereu = 00110 andv = 01. As another example, the string abc has three different rotations, viz. abc itself (withu=abc,v=ε), bca (withu=bc,v=a), and cab (withu=c,v=ab).
It is often useful to define anordering on a set of strings. If the alphabet Σ has atotal order (cf.alphabetical order) one can define a total order on Σ* calledlexicographical order. The lexicographical order istotal if the alphabetical order is, but is notwell-founded for any nontrivial alphabet, even if the alphabetical order is. For 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.
SeeShortlex 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 ...
A number of additional operations on strings commonly occur in the formal theory. These are given in the article onstring operations.
Strings admit the following interpretation as nodes on a graph, wherek is the number of symbols in Σ:
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 thelimit topology, viewing the set of infinite strings as theinverse limit of the sets of finite strings. This is the construction used for thep-adic numbers and some constructions of theCantor set, and yields the same topology.
Isomorphisms between string representations of topologies can be found by normalizing according to thelexicographically minimal string rotation.
String literals (or constants) are called 'anonymous strings'
He invented the terms 'stringology,' which is a subfield of string algorithms,
The term stringology is a popular nickname for string algorithms as well as for text algorithms.
{{cite book}}: CS1 maint: location missing publisher (link)Perl's most famous strength is in string manipulation with regular expressions.
Let Σ be an alphabet. Anonempty word over Σ is a finite sequence with domainIn (for somen ∈ ℕ) and codomain Σ.
Any finite sequence of symbols of a language is called anexpression of that language.
