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 formula_1 is a substring of formula_1 that occurs at the beginning of formula_1; likewise, a suffix of a string formula_1 is a substring that occurs at the end of formula_1. The list of all substrings of  the string ""apple"" would be ""apple"", ""appl"", ""pple"", ""app"", ""ppl"", ""ple"", ""ap"", ""pp"", ""pl"", ""le"", ""a"", ""p"", ""l"", ""e"", "" (note the empty string at the end). Substring. A string formula_6 is a substring (or factor) of a string formula_7 if there exists two strings formula_8 and formula_9 such that formula_10. In particular, the empty string is a substring of every string. Example: The string formula_11codice_1 is equal to substrings (and subsequences) of formula_12codice_2 at two different offsets: The first occurrence is obtained with formula_13codice_3 and formula_14codice_4, while the second occurrence is obtained with formula_13codice_5 and formula_9 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, codice_6 is a prefix of codice_7, which is in turn a suffix of codice_2. If formula_6 is a substring of formula_7, 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). Prefix. A string formula_8 is a prefix of a string formula_7 if there exists a string formula_9 such that formula_22. A "proper prefix" of a string is not equal to the string itself; some sources 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 codice_5 is equal to a prefix (and substring and subsequence) of the string codice_2: The square subset symbol is sometimes used to indicate a prefix, so that formula_23 denotes  that formula_8 is a prefix of formula_7. This defines a binary relation on strings, called the prefix relation, which is a particular kind of prefix order. Suffix. A string formula_9 is a suffix of a string formula_7 if there exists a string formula_8 such that formula_22. A "proper suffix" of a string is not equal to the string itself. A more restricted interpretation is that it is also not empty. A suffix can be seen as a special case of a substring. Example: The string codice_7 is equal to a suffix (and substring and subsequence) of the string codice_2: 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. "bab" is a border of "babab" (and also of "baboon eating a kebab"). Superstring. A superstring of a finite set formula_30 of strings is a single string that contains every string in  formula_30 as a substring. For example, formula_32 is a superstring of formula_33, and formula_34 is a shorter one. Concatenating all members of formula_30, in arbitrary order, always obtains a trivial superstring of formula_30. 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.