{{Short description|Contiguous part of a sequence of symbols}} {{About|the definition of a substring|the computer function which performs this operation|String functions (programming)}} {{Distinguish|text=subsequence, a generalization of substring}} thumb|"''string''" is a substring of "''substring''"
In formal language theory and computer science, a '''substring''' is a contiguous sequence of characters within a string. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequence of "''It was the best of times''", but not a substring.
'''Prefixes''' and '''suffixes''' are special cases of substrings. A prefix of a string <math>S</math> is a substring of <math>S</math> that occurs at the beginning of <math>S</math>; likewise, a suffix of a string <math>S</math> is a substring that occurs at the end of <math>S</math>.
The substrings of the string "{{mono|apple}}" would be: "{{mono|a}}", "{{mono|ap}}", "{{mono|app}}", "{{mono|appl}}", "{{mono|apple}}", "{{mono|p}}", "{{mono|pp}}", "{{mono|ppl}}", "{{mono|pple}}", "{{mono|pl}}", "{{mono|ple}}", "{{mono|l}}", "{{mono|le}}" "{{mono|e}}", "" (note the empty string at the end).
== Substring ==
A string <math>u</math> is a substring (or factor)<ref name=Lot97/> of a string <math>t</math> if there exists two strings <math>p</math> and <math>s</math> such that <math>t = pus</math>. In particular, the empty string is a substring of every string.
Example: The string <math>u=\texttt{ana}</math> is equal to substrings (and subsequences) of <math>t=\texttt{banana}</math> at two different offsets:
banana ||||| ana|| ||| ana
The first occurrence is obtained with <math>p=\texttt{b}</math> and <math>s=\texttt{na}</math>, while the second occurrence is obtained with <math>p=\texttt{ban}</math> and <math>s</math> being the empty string.
A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix; for example, <code>nan</code> is a prefix of <code>nana</code>, which is in turn a suffix of <code>banana</code>. If <math>u</math> is a substring of <math>t</math>, it is also a subsequence, which is a more general concept. The occurrences of a given pattern in a given string can be found with a string searching algorithm. Finding the longest string which is equal to a substring of two or more strings is known as the longest common substring problem. In the mathematical literature, substrings are also called '''subwords''' (in America) or '''factors''' (in Europe). {{citation needed|date=November 2020}}
== Prefix == {{see also|String operations#Prefixes}} A string <math>p</math> is a prefix<ref name=Lot97/> of a string <math>t</math> if there exists a string <math>s</math> such that <math>t = ps</math>. A ''proper prefix'' of a string is not equal to the string itself;<ref name=Kel95/> some sources<ref name=Gus97/> in addition restrict a proper prefix to be non-empty. A prefix can be seen as a special case of a substring.
Example: The string <code>ban</code> is equal to a prefix (and substring and subsequence) of the string <code>banana</code>:
banana ||| ban
The square subset symbol is sometimes used to indicate a prefix, so that <math>p \sqsubseteq t</math> denotes that <math>p</math> is a prefix of <math>t</math>. This defines a binary relation on strings, called the prefix relation, which is a particular kind of prefix order.
== Suffix ==
A string <math>s</math> is a suffix<ref name=Lot97/> of a string <math>t</math> if there exists a string <math>p</math> such that <math>t = ps</math>. A ''proper suffix'' of a string is not equal to the string itself. A more restricted interpretation is that it is also not empty.{{ref|Gus97}} A suffix can be seen as a special case of a substring.
Example: The string <code>nana</code> is equal to a suffix (and substring and subsequence) of the string <code>banana</code>:
banana |||| nana
A suffix tree for a string is a trie data structure that represents all of its suffixes. Suffix trees have large numbers of applications in string algorithms. The suffix array is a simplified version of this data structure that lists the start positions of the suffixes in alphabetically sorted order; it has many of the same applications.
== Border ==
A border is suffix and prefix of the same string, e.g. "<math>\texttt{bab}</math>" is a border of "<math>\texttt{babab}</math>" (and also of "<math>\texttt{baboon}\,\,\texttt{eating}\,\,\texttt{a}\,\,\texttt{kebab}</math>").{{citation needed|date=January 2022}}
== Superstring ==
A '''superstring''' of a finite set <math>P</math> of strings is a single string that contains every string in <math>P</math> as a substring. For example, <math>\texttt{bcclabccefab}</math> is a superstring of <math>P = \{\texttt{abcc}, \texttt{efab}, \texttt{bccla}\}</math>, and <math>\texttt{efabccla}</math> is a shorter one. Concatenating all members of <math>P</math>, in arbitrary order, always obtains a trivial superstring of <math>P</math>. Finding superstrings whose length is as small as possible is a more interesting problem.
A string that contains every possible permutation of a specified character set is called a superpermutation.
== See also == * Substring index * Suffix automaton
==References== {{Reflist|refs= <ref name=Gus97>{{cite book | last = Gusfield | first = Dan | orig-year = 1997 | year = 1999 | title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology | publisher = Cambridge University Press | location = US | isbn = 0-521-58519-8 }}</ref> <ref name=Kel95>{{cite book | last = Kelley | first = Dean | year = 1995 | title = Automata and Formal Languages: An Introduction | publisher = Prentice-Hall International | location = London | isbn = 0-13-497777-7 }}</ref> <ref name=Lot97>{{cite book | last = Lothaire | first = M. | year = 1997 | title = Combinatorics on words | publisher = Cambridge University Press | location = Cambridge | isbn = 0-521-59924-5 }}</ref> }}
Category:String (computer science) Category:Formal languages