Contents 1 Formal theory 1.1 Concatenation and substrings 1.2 Prefixes and suffixes 1.3 Rotations 1.4 Reversal 1.5 Lexicographical ordering 1.6 String operations 1.7 Topology 2 String datatypes 2.1 String length 2.2 Character encoding 2.3 Implementations 2.4 Representations 2.4.1 Null-terminated 2.4.2 Byte- and bit-terminated 2.4.3 Length-prefixed 2.4.4 Strings as records 2.4.5 Other representations 2.5 Security concerns 3 Literal strings 4 Non-text strings 5 String processing algorithms 6 Character string-oriented languages and utilities 7 Character string functions 8 String buffers 8.1 In Java 8.1.1 Theory 8.1.2 Implications 8.2 In .NET 8.3 In other languages 8.4 String instructions 9 See also 10 References


Formal theory[edit] See also: Tuple Let Σ be a non-empty finite set of symbols (alternatively called characters), called the alphabet. No assumption is made about the nature of the symbols. A string (or word) over Σ is any finite sequence of symbols from Σ.[2] For example, if Σ = {0, 1}, then 01011 is a string over Σ. The length of a string s is the number of symbols in s (the length of the sequence) and can be any non-negative integer; it is often denoted as |s|. The empty string is the unique string over Σ of length 0, and is denoted ε or λ.[2][3] The set of all strings over Σ of length n is denoted Σn. For example, if Σ = {0, 1}, then Σ2 = {00, 01, 10, 11}. Note that Σ0 = {ε} for any alphabet Σ. The set of all strings over Σ of any length is the Kleene closure of Σ and is denoted Σ*. In terms of Σn, Σ ∗ = ⋃ n ∈ N ∪ { 0 } Σ n {\displaystyle \Sigma ^{*}=\bigcup _{n\in \mathbb {N} \cup \{0\}}\Sigma ^{n}} For example, if Σ = {0, 1}, then Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, ...}. Although the set Σ* itself is countably infinite, each element of Σ* is a string of finite length. A set of strings over Σ (i.e. any subset of Σ*) is called a formal language over Σ. For example, if Σ = {0, 1}, the set of strings with an even number of zeros, {ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, ...}, is a formal language over Σ. Concatenation and substrings[edit] Concatenation is an important binary operation on Σ*. For any two strings s and t in Σ*, their concatenation is defined as the sequence of symbols in s followed by the sequence of characters in t, and is denoted st. For example, if Σ = {a, b, ..., z}, s = bear, and t = hug, then st = bearhug and ts = hugbear. String concatenation is an associative, but non-commutative operation. The empty string ε serves as the identity element; for any string s, εs = sε = s. Therefore, the set Σ* and the concatenation operation form a monoid, the free monoid generated by Σ. In addition, the length function defines a monoid homomorphism from Σ* to the non-negative integers (that is, a function L : Σ ∗ ↦ N ∪ { 0 } {\displaystyle L:\Sigma ^{*}\mapsto \mathbb {N} \cup \{0\}} , such that L ( s t ) = L ( s ) + L ( t ) ∀ s , t ∈ Σ ∗ {\displaystyle L(st)=L(s)+L(t)\quad \forall s,t\in \Sigma ^{*}} ). A string s is said to be a substring or factor of t if there exist (possibly empty) strings u and v such that t = usv. The relation "is a substring of" defines a partial order on Σ*, the least element of which is the empty string. Prefixes and suffixes[edit] A string s is said to be a prefix of t if there exists a string u such that t = su. If u is nonempty, s is said to be a proper prefix of t. Symmetrically, a string s is said to be a suffix of t if there exists a string u such that t = us. If u is nonempty, s is said to be a proper suffix of t. Suffixes and prefixes are substrings of t. Both the relations "is a prefix of" and "is a suffix of" are prefix orders. Rotations[edit] A string s = uv is said to be a rotation of t if t = vu. For example, if Σ = {0, 1} the string 0011001 is a rotation of 0100110, where u = 00110 and v = 01. Reversal[edit] The reverse of a string is a string with the same symbols but in reverse order. For example, if s = abc (where a, b, and c are symbols of the alphabet), then the reverse of s is cba. A string that is the reverse of itself (e.g., s = madam) is called a palindrome, which also includes the empty string and all strings of length 1. Lexicographical ordering[edit] It is often useful to define an ordering on a set of strings. If the alphabet Σ has a total order (cf. alphabetical order) one can define a total order on Σ* called lexicographical order. For example, if Σ = {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 ... The lexicographical order is total if the alphabetical order is, but isn't well-founded for any nontrivial alphabet, even if the alphabetical order is. See Shortlex for an alternative string ordering that preserves well-foundedness. String operations[edit] A number of additional operations on strings commonly occur in the formal theory. These are given in the article on string operations. Topology[edit] (Hyper)cube of binary strings of length 3 Strings admit the following interpretation as nodes on a graph: Fixed-length strings can be viewed as nodes on a hypercube Variable-length strings (of finite length) can be viewed as nodes on the k-ary tree, where k is the number of symbols in Σ Infinite strings (otherwise not considered here) can be viewed as infinite paths on the k-ary tree. The natural topology on the set of fixed-length strings or variable-length strings is the discrete topology, but the natural topology on the set of infinite strings is the limit topology, viewing the set of infinite strings as the inverse limit of the sets of finite strings. This is the construction used for the p-adic numbers and some constructions of the Cantor set, and yields the same topology. Isomorphisms between string representations of topologies can be found by normalizing according to the lexicographically minimal string rotation.


String datatypes[edit] See also: Comparison of programming languages (string functions) A string datatype is a datatype modeled on the idea of a formal string. Strings are such an important and useful datatype that they are implemented in nearly every programming language. In some languages they are available as primitive types and in others as composite types. The syntax of most high-level programming languages allows for a string, usually quoted in some way, to represent an instance of a string datatype; such a meta-string is called a literal or string literal. String length[edit] Although formal strings can have an arbitrary (but finite) length, the length of strings in real languages is often constrained to an artificial maximum. In general, there are two types of string datatypes: fixed-length strings, which have a fixed maximum length to be determined at 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. Most strings in modern programming languages are variable-length strings. Of course, even variable-length strings are limited in length – by the number of bits available to a pointer, and by the size of available computer memory. The string length can be stored as a separate integer (which may put an artificial limit on the length) or implicitly through a termination character, usually a character value with all bits zero. See also "Null-terminated" below. Character encoding[edit] String datatypes have historically allocated one byte per character, and, although the exact character set varied by region, character encodings were similar enough that programmers could often get away with ignoring this, since characters a program treated specially (such as period and space and comma) were in the same place in all the encodings a program would encounter. These character sets were typically based on ASCII or EBCDIC. If text in one encoding was displayed on a system using a different encoding, text was often mangled, though often somewhat readable and some computer users learned to read the mangled text. Logographic languages such as Chinese, Japanese, and Korean (known collectively as CJK) need far more than 256 characters (the limit of a one 8-bit byte per-character encoding) for reasonable representation. The normal solutions involved keeping single-byte representations for ASCII and using two-byte representations for CJK ideographs. Use of these with existing code led to problems with matching and cutting of strings, the severity of which depended on how the character encoding was designed. Some encodings such as the EUC family guarantee that a byte value in the ASCII range will represent only that ASCII character, making the encoding safe for systems that use those characters as field separators. Other encodings such as ISO-2022 and Shift-JIS do not make such guarantees, making matching on byte codes unsafe. These encodings also were not "self-synchronizing", so that locating character boundaries required backing up to the start of a string, and pasting two strings together could result in corruption of the second string. Unicode has simplified the picture somewhat. Most programming languages now have a datatype for Unicode strings. Unicode's preferred byte stream format UTF-8 is designed not to have the problems described above for older multibyte encodings. UTF-8, UTF-16 and UTF-32 require the programmer to know that the fixed-size code units are different than the "characters", the main difficulty currently is incorrectly designed APIs that attempt to hide this difference (UTF-32 does make code points fixed-sized, but these are not "characters" due to composing codes). Implementations[edit] Some languages like C++ implement strings as templates that can be used with any datatype, but this is the exception, not the rule. Some languages, such as C++ and Ruby, normally allow the contents of a string to be changed after it has been created; these are termed mutable strings. In other languages, such as Java and Python, the value is fixed and a new string must be created if any alteration is to be made; these are termed immutable strings. Strings are typically implemented as arrays of bytes, characters, or code units, in order to allow fast access to individual units or substrings—including characters when they have a fixed length. A few languages such as Haskell implement them as linked lists instead. Some languages, such as Prolog and Erlang, avoid implementing a dedicated string datatype at all, instead adopting the convention of representing strings as lists of character codes. Representations[edit] Representations of strings depend heavily on the choice of character repertoire and the method of character encoding. Older string implementations were designed to work with repertoire and encoding defined by ASCII, or more recent extensions like the ISO 8859 series. Modern implementations often use the extensive repertoire defined by Unicode along with a variety of complex encodings such as UTF-8 and UTF-16. The term byte string usually indicates a general-purpose string of bytes, rather than strings of only (readable) characters, strings of bits, or such. Byte strings often imply that bytes can take any value and any data can be stored as-is, meaning that there should be no value interpreted as a termination value. Most string implementations are very similar to variable-length arrays with the entries storing the character codes of corresponding characters. The principal difference is that, with certain encodings, a single logical character may take up more than one entry in the array. This happens for example with UTF-8, where single codes (UCS code points) can take anywhere from one to four bytes, and single characters can take an arbitrary number of codes. In these cases, the logical length of the string (number of characters) differs from the physical length of the array (number of bytes in use). UTF-32 avoids the first part of the problem. Null-terminated[edit] Main article: Null-terminated string The length of a string can be stored implicitly by using a special terminating character; often this is the null character (NUL), which has all bits zero, a convention used and perpetuated by the popular C programming language.[4] Hence, this representation is commonly referred to as a C string. This representation of an n-character string takes n + 1 space (1 for the terminator), and is thus an implicit data structure. In terminated strings, the terminating code is not an allowable character in any string. Strings with length field do not have this limitation and can also store arbitrary binary data. An example of a null-terminated string stored in a 10-byte buffer, along with its ASCII (or more modern UTF-8) representation as 8-bit hexadecimal numbers is: 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 called ASCIZ strings, after the original assembly language directive used to declare them.) Byte- and bit-terminated[edit] Using a special byte other than null for terminating strings has historically appeared in both hardware and software, though sometimes with a value that was also a printing character. $ was used by many assembler systems, : used by CDC systems (this character had a value of zero), and the ZX80 used "[5] since this was the string delimiter in its BASIC language. Somewhat similar, "data processing" machines like the IBM 1401 used a special word mark bit to delimit strings at the left, where the operation would start at the right. This bit had to be clear in all other parts of the string. This meant that, while the IBM 1401 had a seven-bit word, almost no-one ever thought to use this as a feature, and override the assignment of the seventh bit to (for example) handle ASCII codes. Early microcomputer software relied upon the fact that ASCII codes do not use the high-order bit, and set it to indicate the end of a string. It must be reset to 0 prior to output.[6] Length-prefixed[edit] The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value; a convention used in many Pascal dialects, as a consequence, some people call such a string a Pascal string or P-string. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit words to store the string length. When the length field covers the address space, strings are limited only by the available memory. If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an implicit data structure, taking n + k space, where k is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.). If the length is not bounded, encoding a length n takes log(n) space (see fixed-length code), so length-prefixed strings are a succinct data structure, encoding a string of length n in log(n) + n space. In the latter case, the length-prefix field itself doesn't have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased. Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation: length F R A N K k e f w 0516 4616 5216 4116 4E16 4B16 6B16 6516 6616 7716 Strings as records[edit] Many languages, including object-oriented ones, implement strings as records with an internal structure like: class string { size_t length; char *text; }; However, since the implementation is usually hidden, the string must be accessed and modified through member functions. text is a pointer to a dynamically allocated memory area, which might be expanded as needed. See also string (C++). Other representations[edit] Both character termination and length codes limit strings: For example, C character arrays that contain null (NUL) characters cannot be handled directly by C string library functions: Strings using a length code are limited to the maximum value of the length code. Both of these limitations can be overcome by clever programming. It is possible to create data structures and functions that manipulate them that do not have the problems associated with character termination and can in principle overcome length code bounds. It is also possible to optimize the string represented using techniques from run length encoding (replacing repeated characters by the character value and a length) and Hamming encoding[clarification needed]. While these representations are common, others are possible. Using ropes makes certain string operations, such as insertions, deletions, and concatenations more efficient. The core data structure in a text editor is the one that manages the string (sequence of characters) that represents the current state of the file being edited. While that state could be stored in a single long consecutive array of characters, a typical text editor instead uses an alternative representation as its sequence data structure—a gap buffer, a linked list of lines, a piece table, or a rope—which makes certain string operations, such as insertions, deletions, and undoing previous edits, more efficient.[7] Security concerns[edit] The differing memory layout and storage requirements of strings can affect the security of the program accessing the string data. String representations requiring a terminating character are commonly susceptible to buffer overflow problems if the terminating character is not present, caused by a coding error or an attacker deliberately altering the data. String representations adopting a separate length field are also susceptible if the length can be manipulated. In such cases, program code accessing the string data requires bounds checking to ensure that it does not inadvertently access or change data outside of the string memory limits. String data is frequently obtained from user-input to a program. As such, it is the responsibility of the program to validate the string to ensure that it represents the expected format. Performing limited or no validation of user-input can cause a program to be vulnerable to code injection attacks.


Literal strings[edit] See also: String literal Sometimes, strings need to be embedded inside a text file that is both human-readable and intended for consumption by a machine. This is needed in, for example, source code of programming languages, or in configuration files. In this case, the NUL character doesn't work well as a terminator since it is normally invisible (non-printable) and is difficult to input via a keyboard. Storing the string length would also be inconvenient as manual computation and tracking of the length is tedious and error-prone. Two common representations are: Surrounded by quotation marks (ASCII 0x22 double quote or ASCII 0x27 single quote), used by most programming languages. To be able to include special characters such as the quotation mark itself, newline characters, or non-printable characters, escape sequences are often available, usually prefixed with the backslash character (ASCII 0x5C). Terminated by a newline sequence, for example in Windows INI files.


Non-text strings[edit] While character strings are very common uses of strings, a string in computer science may refer generically to any sequence of homogeneously typed data. A bit string or byte string, for example, may be used to represent non-textual binary data retrieved from a communications medium. This data may or may not be represented by a string-specific datatype, depending on the needs of the application, the desire of the programmer, and the capabilities of the programming language being used. If the programming language's string implementation is not 8-bit clean, data corruption may ensue. C programmers draw a sharp distinction between a "string", aka a "string of characters", which by definition is always null terminated, vs. a "byte string" or "pseudo string" which may be stored in the same array but is often not null terminated. Using C string handling functions on such a "byte string" often seems to work, but later leads to security problems.[8][9][10]


String processing algorithms[edit] There are many algorithms for processing strings, each with various trade-offs. Some categories of algorithms include: String searching algorithms for finding a given substring or pattern String manipulation algorithms Sorting algorithms Regular expression algorithms Parsing a string Sequence mining Advanced string algorithms often employ complex mechanisms and data structures, among them suffix trees and finite state machines. The name stringology was coined in 1984 by computer scientist Zvi Galil for the issue of algorithms and data structures used for string processing.[11]


Character string-oriented languages and utilities[edit] Character strings are such a useful datatype that several languages have been designed in order to make string processing applications easy to write. Examples include the following languages: awk Icon MUMPS Perl Rexx Ruby sed SNOBOL Tcl TTM Many Unix utilities perform simple string manipulations and can be used to easily program some powerful string processing algorithms. Files and finite streams may be viewed as strings. Some APIs like Multimedia Control Interface, embedded SQL or printf use strings to hold commands that will be interpreted. Recent scripting programming languages, including Perl, Python, Ruby, and Tcl employ regular expressions to facilitate text operations. Perl is particularly noted for its regular expression use,[12] and many other languages and applications implement Perl compatible regular expressions. Some languages such as Perl and Ruby support string interpolation, which permits arbitrary expressions to be evaluated and included in string literals.


Character string functions[edit] See also: Comparison of programming languages (string functions) String functions are used to manipulate a string or change or edit the contents of a string. They also are used to query information about a string. They are usually used within the context of a computer programming language. The most basic example of a string function is the string length function – the function that returns the length of a string (not counting any terminator characters or any of the string's internal structural information) and does not modify the string. This function is often named length or len. For example, length("hello world") would return 11.


String buffers[edit] In some programming languages, a string buffer is an alternative to a string. It has the ability to be altered through adding or appending, whereas a String is normally fixed or immutable. In Java[edit] Theory[edit] Java's standard way to handle text is to use its String class. Any given String in Java is an immutable object, which means its state cannot be changed. A String has an array of characters. Whenever a String must be manipulated, any changes require the creation of a new String (which, in turn, involves the creation of a new array of characters, and copying of the original array). This happens even if the original String's value or intermediate Strings used for the manipulation are not kept. Java provides two alternate classes for string manipulation, called StringBuffer and StringBuilder. Both of these, like String, each has an array to hold characters. They, however, are mutable (its state can be altered). Their array of characters is not necessarily completely filled (as opposed to a String, whose array is always the exact required length for its contents). Thus, a StringBuffer or StringBuilder has the capability to add, remove, or change its state without creating a new object (and without the creation of a new array, and array copying). The exception to this is when its array is no longer of suitable length to hold its content (a case which rarely happens because of the default Dynamic memory allocation provided by the JVM). In this case, it is required to create a new array, and copy the contents. For these reasons, Java would handle an expression like String newString = aString + anInt + aChar + aDouble; like this: String newString = (new StringBuilder(aString)).append(anInt).append(aChar).append(aDouble).toString(); Implications[edit] Generally, a StringBuffer is more efficient than a String in string handling. However, this is not necessarily the case, since a StringBuffer will be required to recreate its character array when it runs out of space. Theoretically, this is possible to happen the same number of times as a new String would be required, although this is unlikely (and the programmer can provide length hints to prevent this). Either way, the effect is not noticeable in modern desktop computers. As well, the shortcomings of arrays are inherent in a StringBuffer. In order to insert or remove characters at arbitrary positions, whole sections of arrays must be moved. The method by which a StringBuffer is attractive in an environment with low processing power takes this ability by using too much memory, which is likely also at a premium in this environment. This point, however, is trivial, considering the space required for creating many instances of Strings in order to process them. As well, the StringBuffer can be optimized to "waste" as little memory as possible. The StringBuilder class, introduced in J2SE 5.0, differs from StringBuffer in that it is unsynchronized. When only a single thread at a time will access the object, using a StringBuilder processes more efficiently than using a StringBuffer. StringBuffer and StringBuilder are included in the java.lang package. In .NET[edit] Microsoft's .NET Framework has a StringBuilder class in its Base Class Library. In other languages[edit] In C++ and Ruby, the standard string class is already mutable, with the ability to change the contents and append strings, etc., so a separate mutable string class is unnecessary. In Objective-C (Cocoa/OpenStep frameworks), the NSMutableString class is the mutable version of the NSString class. String instructions[edit] Some microprocessor's instruction set architectures contain direct support for string operations, such as block copy (e.g. In intel x86m REPNZ MOVSB).[13]


See also[edit] Formal language — a (possibly infinite) set of strings in theoretical computer science Connection string — passed to a driver to initiate a connection e.g. to a database Rope — a data structure for efficiently manipulating long strings Bitstring — a string of binary digits Binary-safe — a property of string manipulating functions treating their input as raw data stream Improper input validation — a type of software security vulnerability particularly relevant for user-given strings Incompressible string — a string that cannot be compressed by any algorithm Empty string — its properties and representation in programming languages String metric — notions of similarity between strings string (C++) — overview of C++ string handling string.h — overview of C string handling Analysis of algorithms — determining time and storage needed by a particular (e.g. string manipulation) algorithm Comparison of programming languages (string functions)


References[edit] ^ "Introduction To Java - MFC 158 G". String literals (or constants) are called ‘anonymous strings’  ^ a b Barbara H. Partee; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer.  ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley. ISBN 0-201-02988-X.  Here: sect.1.1, p.1 ^ Bryant, Randal E.; David, O'Hallaron (2003), Computer Systems: A Programmer's Perspective (2003 ed.), Upper Saddle River, NJ: Pearson Education, p. 40, ISBN 0-13-034074-X  ^ Wearmouth, Geoff. "An Assembly Listing of the ROM of the Sinclair ZX80". Archived from the original on August 15, 2015. CS1 maint: Unfit url (link) ^ Allison, Dennis. "Design Notes for Tiny BASIC".  ^ Charles Crowley. "Data Structures for Text Sequences". Section "Introduction". ^ "strlcpy and strlcat - consistent, safe, string copy and concatenation." ^ "A rant about strcpy, strncpy and strlcpy." ^ Keith Thompson. "No, strncpy() is not a "safer" strcpy()". 2012. ^ "The Prague Stringology Club". stringology.org. Retrieved 23 May 2015.  ^ "Essential Perl". Perl's most famous strength is in string manipulation with regular expressions.  ^ "x86 string instructions".  v t e Strings String metric Approximate string matching Bitap algorithm Damerau–Levenshtein distance Edit distance Hamming distance Jaro–Winkler distance Lee distance Levenshtein automaton Levenshtein distance Wagner–Fischer algorithm String searching algorithm Apostolico–Giancarlo algorithm Boyer–Moore string search algorithm Boyer–Moore–Horspool algorithm Knuth–Morris–Pratt algorithm Rabin–Karp string search algorithm Multiple string searching Aho–Corasick Commentz-Walter algorithm Rabin–Karp Regular expression Comparison of regular expression engines Regular tree grammar Thompson's construction Nondeterministic finite automaton Sequence alignment Hirschberg's algorithm Needleman–Wunsch algorithm Smith–Waterman algorithm Data structures DAFSA Suffix array Suffix automaton Suffix tree Generalized suffix tree Rope Ternary search tree Trie Other Parsing Pattern matching Compressed pattern matching Longest common subsequence Longest common substring Sequential pattern mining Sorting v t e Data types Uninterpreted Bit Byte Trit Tryte Word Bit array Numeric Arbitrary-precision or bignum Complex Decimal Fixed point Floating point Double precision Extended precision Half precision Long double Minifloat Octuple precision Quadruple precision Single precision Integer signedness Interval Rational Pointer Address physical virtual Reference Text Character String null-terminated Composite Algebraic data type generalized Array Associative array Class Dependent Equality Inductive List Object metaobject Option type Product Record Set Union tagged Other Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void Related topics Abstract data type Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Protocol interface Subtyping Type constructor Type conversion Type system See also platform-dependent and independent units of information v t e Automata theory: formal languages and formal grammars Chomsky hierarchy Grammars Languages Abstract machines Type-0 — Type-1 — — — — — Type-2 — — Type-3 — — Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive Recursively enumerable Decidable Context-sensitive Positive range concatenation* Indexed* — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton restricted Tree stack automaton Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite Each category of languages, except those marked by a *, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line. Retrieved from "https://en.wikipedia.org/w/index.php?title=String_(computer_science)&oldid=816633018" Categories: Character encodingData typesFormal languagesCombinatorics on wordsPrimitive typesSyntactic entitiesString (computer science)Algorithms on stringsHidden categories: CS1 maint: Unfit urlArticles needing additional references from March 2015All articles needing additional referencesWikipedia articles needing clarification from June 2015


Navigation menu Personal tools Not logged inTalkContributionsCreate accountLog in Namespaces ArticleTalk Variants Views ReadEditView history More Search Navigation Main pageContentsFeatured contentCurrent eventsRandom articleDonate to WikipediaWikipedia store Interaction HelpAbout WikipediaCommunity portalRecent changesContact page Tools What links hereRelated changesUpload fileSpecial pagesPermanent linkPage informationWikidata itemCite this page Print/export Create a bookDownload as PDFPrintable version Languages العربيةBân-lâm-gúБеларускаяБългарскиCatalàČeštinaDanskDeutschEestiΕλληνικάEspañolEsperantoفارسیFrançais한국어Bahasa IndonesiaÍslenskaItalianoעבריתMagyarമലയാളംBahasa MelayuNederlands日本語NorskPolskiPortuguêsРусскийScotsکوردیСрпски / srpskiSuomiSvenskaTagalogதமிழ்ไทยУкраїнська中文 Edit links This page was last edited on 22 December 2017, at 16:59. Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization. Privacy policy About Wikipedia Disclaimers Contact Wikipedia Developers Cookie statement Mobile view (window.RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.316","walltime":"0.419","ppvisitednodes":{"value":1692,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":73867,"limit":2097152},"templateargumentsize":{"value":5813,"limit":2097152},"expansiondepth":{"value":11,"limit":40},"expensivefunctioncount":{"value":2,"limit":500},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 272.161 1 -total"," 40.54% 110.339 1 Template:Reflist"," 22.07% 60.065 6 Template:Cite_web"," 14.71% 40.040 1 Template:Clarify"," 13.72% 37.350 1 Template:Fix-span"," 13.24% 36.034 1 Template:Refimprove"," 10.94% 29.768 1 Template:Ambox"," 8.78% 23.896 1 Template:Replace"," 8.10% 22.043 1 Template:About"," 7.07% 19.241 3 Template:Navbox"]},"scribunto":{"limitreport-timeusage":{"value":"0.119","limit":"10.000"},"limitreport-memusage":{"value":4752014,"limit":52428800}},"cachereport":{"origin":"mw1218","timestamp":"20180114165629","ttl":1900800,"transientcontent":false}}});});(window.RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgBackendResponseTime":108,"wgHostname":"mw1244"});});


String_(computer_science) - Photos and All Basic Informations

String_(computer_science) More Links

String (disambiguation)Wikipedia:VerifiabilityHelp:Introduction To Referencing With Wiki Markup/1Help:Maintenance Template RemovalEnlargeBioinformaticsDNANitrogenous BaseComputer ProgrammingSequenceCharacter (computing)Literal (computer Programming)Data TypeArray Data StructureByteWord (computer Architecture)Character EncodingArray Data TypeList (abstract Data Type)Variable (programming)Dynamic AllocationSource CodeString LiteralFormal LanguageMathematical LogicTheoretical Computer ScienceSymbol (formal)Set (mathematics)Alphabet (computer Science)TupleEmpty SetFinite SetAlphabet (formal Languages)SequenceLengthNon-negative IntegerEmpty StringKleene StarCountably InfiniteSubsetConcatenationBinary OperationAssociativeCommutativeIdentity ElementMonoidFree MonoidMonoid HomomorphismSubstringBinary RelationPartial OrderLeast ElementSubstringSubstringPrefix OrderPalindromeOrder TheoryTotal OrderAlphabetical OrderLexicographical OrderTotal OrderWell-foundedShortlexString OperationsEnlargeHypercubeK-ary TreeInfinite StringK-ary TreeK-ary TreeLimit TopologyInverse LimitP-adicCantor SetIsomorphismLexicographically Minimal String RotationComparison Of Programming Languages (string Functions)Programming LanguagePrimitive TypeComposite TypeSyntaxMemory ManagementProgramming LanguagesComputer MemoryASCIIEBCDICMojibakeLogographChinese LanguageJapanese LanguageKorean LanguageCJKIdeographsExtended Unix CodeISO-2022Shift-JISUnicodeUTF-8UTF-32C++Generic ProgrammingRuby (programming Language)Java (programming Language)Python (programming Language)Array Data TypeHaskell (programming Language)Linked ListPrologErlang (programming Language)ISO 8859Array Data TypeCharacter CodeUniversal Character SetUTF-32Null-terminated StringNull CharacterC (programming Language)Implicit Data StructureBinary DataBuffer (computer Science)ASCIIUTF-8Hexadecimal NumberNull CharacterHexadecimalAssembly LanguageControl Data CorporationZX80IBM 1401Word Mark (computer Hardware)Pascal (programming Language)Word (data Type)Address SpaceDynamic Memory AllocationImplicit Data StructureFixed-length CodeSuccinct Data StructureRecord (computer Science)Information HidingString (C++)Run-length EncodingHamming CodingWikipedia:Please ClarifyRope (data Structure)Text EditorGap BufferLinked ListPiece TableRope (data Structure)Buffer OverflowHacker (computer Security)Bounds CheckingCode InjectionString LiteralQuotation MarkHexadecimalEscape CharacterBackslashNewlineINI FileBit StringByte StringBinary Data8-bit CleanC String HandlingString (computer Science)AlgorithmString Searching AlgorithmString Manipulation AlgorithmSorting AlgorithmRegular ExpressionParserSequence MiningSuffix TreeFinite State MachineZvi GalilAWK (programming Language)Icon (programming Language)MUMPSPerlRexxRuby (programming Language)SedSNOBOLTclTTM (programming Language)UnixApplication Programming InterfaceMultimedia Control InterfaceEmbedded SQLPrintfScripting Programming LanguagePython (programming Language)Regular ExpressionPerl Compatible Regular ExpressionsString InterpolationComparison Of Programming Languages (string Functions)String FunctionProgramming LanguageString LengthComparison Of Programming Languages (string Functions)Programming LanguageImmutable ObjectJava (Sun)Class (computer Science)Immutable ObjectState (computer Science)Array Data TypeCharacter (computing)Analysis Of AlgorithmsJava Platform, Standard EditionSynchronization (computer Science)Thread (computer Science).NET FrameworkBase Class LibraryC++Ruby (programming Language)Objective-CCocoa (API)OpenStepMicroprocessorInstruction Set ArchitectureIntel X86Formal LanguageConnection StringRope (computer Science)BitstringBinary-safeImproper Input ValidationIncompressible StringEmpty StringString MetricString (C++)String.hAnalysis Of AlgorithmsComparison Of Programming Languages (string Functions)International Standard Book NumberSpecial:BookSources/0-201-02988-XRandal BryantInternational Standard Book NumberSpecial:BookSources/0-13-034074-XCategory:CS1 Maint: Unfit UrlTemplate:StringsTemplate Talk:StringsString MetricApproximate String MatchingBitap AlgorithmDamerau–Levenshtein DistanceEdit DistanceHamming DistanceJaro–Winkler DistanceLee DistanceLevenshtein AutomatonLevenshtein DistanceWagner–Fischer AlgorithmString Searching AlgorithmApostolico–Giancarlo AlgorithmBoyer–Moore String Search AlgorithmBoyer–Moore–Horspool AlgorithmKnuth–Morris–Pratt AlgorithmRabin–Karp AlgorithmAho–Corasick AlgorithmCommentz-Walter AlgorithmRabin–Karp AlgorithmRegular ExpressionComparison Of Regular Expression EnginesRegular Tree GrammarThompson's ConstructionNondeterministic Finite AutomatonSequence AlignmentHirschberg's AlgorithmNeedleman–Wunsch AlgorithmSmith–Waterman AlgorithmCategory:String Data StructuresDeterministic Acyclic Finite State AutomatonSuffix ArraySuffix AutomatonSuffix TreeGeneralized Suffix TreeRope (data Structure)Ternary Search TreeTrieParsingPattern MatchingCompressed Pattern MatchingLongest Common SubsequenceLongest Common SubstringSequential Pattern MiningCategory:String Sorting AlgorithmsTemplate:Data TypesTemplate Talk:Data TypesData TypeUnits Of InformationBitByteTernary Numeral SystemTernary Numeral SystemWord (computer Architecture)Bit ArrayArbitrary-precision ArithmeticComplex Data TypeDecimal Data TypeFixed-point ArithmeticFloating PointDouble-precision Floating-point FormatExtended PrecisionHalf-precision Floating-point FormatLong DoubleMinifloatOctuple-precision Floating-point FormatQuadruple-precision Floating-point FormatSingle-precision Floating-point FormatInteger (computer Science)SignednessInterval ArithmeticRational Data TypePointer (computer Programming)Memory AddressPhysical AddressVirtual Address SpaceReference (computer Science)Plain TextCharacter (computing)Null-terminated StringComposite Data TypeAlgebraic Data TypeGeneralized Algebraic Data TypeArray Data TypeAssociative ArrayClass (computer Programming)Dependent TypeIntuitionistic Type TheoryInductive TypeList (abstract Data Type)Object (computer Science)MetaobjectOption TypeProduct TypeRecord (computer Science)Set (abstract Data Type)Union TypeTagged UnionBoolean Data TypeBottom TypeContainer (abstract Data Type)Enumerated TypeException HandlingFunction TypeOpaque Data TypeRecursive Data TypeSemaphore (programming)Stream (computing)Top TypeType ClassUnit TypeVoid TypeAbstract Data TypeData StructureGeneric ProgrammingKind (type Theory)MetaclassParametric PolymorphismPrimitive Data TypeProtocol (object-oriented Programming)Interface (computing)SubtypingType ConstructorType ConversionType SystemTemplate:Information UnitsTemplate:Formal Languages And GrammarsTemplate Talk:Formal Languages And GrammarsAutomata TheoryFormal LanguageFormal GrammarChomsky HierarchyFormal GrammarFormal LanguageAbstract MachineUnrestricted GrammarContext-sensitive GrammarRange Concatenation GrammarsIndexed GrammarLinear Context-free Rewriting SystemTree-adjoining GrammarContext-free GrammarDeterministic Context-free GrammarNested WordRegular GrammarNon-recursive GrammarRecursively Enumerable LanguageRecursive LanguageContext-sensitive LanguageRange Concatenation LanguageIndexed LanguageLinear Context-free Rewriting LanguageTree-adjoining GrammarContext-free LanguageDeterministic Context-free LanguageNested WordRegular LanguageStar-free LanguageFinite LanguageTuring MachineMachine That Always HaltsLinear Bounded AutomatonPTIMENested Stack AutomatonThread AutomatonTree Stack AutomatonEmbedded Pushdown AutomatonPushdown AutomatonDeterministic Pushdown AutomatonNested WordFinite-state MachineAperiodic Finite State AutomatonDeterministic Acyclic Finite State AutomatonProper SubsetHelp:CategoryCategory:Character EncodingCategory:Data TypesCategory:Formal LanguagesCategory:Combinatorics On WordsCategory:Primitive TypesCategory:Syntactic EntitiesCategory:String (computer Science)Category:Algorithms On StringsCategory:CS1 Maint: Unfit UrlCategory:Articles Needing Additional References From March 2015Category:All Articles Needing Additional ReferencesCategory:Wikipedia Articles Needing Clarification From June 2015Discussion About Edits From This IP Address [n]A List Of Edits Made From This IP Address [y]View The Content Page [c]Discussion About The Content Page [t]Edit This Page [e]Visit The Main Page [z]Guides To Browsing WikipediaFeatured Content – The Best Of WikipediaFind Background Information On Current EventsLoad A Random Article [x]Guidance On How To Use And Edit WikipediaFind Out About WikipediaAbout The Project, What You Can Do, Where To Find ThingsA List Of Recent Changes In The Wiki [r]List Of All English Wikipedia Pages Containing Links To This Page [j]Recent Changes In Pages Linked From This Page [k]Upload Files [u]A List Of All Special Pages [q]Wikipedia:AboutWikipedia:General Disclaimer



view link view link view link view link view link