- Substring
A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved. In this context, the terms "string" and "
sequence " have the same meaning.Subsequence
:"Main article
subsequence "A subsequence of a string T = t_1 t_2 dots t_n is a string hat T = t_{i_1} dots t_{i_m} such that i_1 < dots < i_m, where m leq n. Subsequence is a generalisation of substring, suffix and prefix. Finding the longest string which is equal to a subsequence of two or more strings is known as the
longest common subsequence problem .Example: The string
anna
is equal to a subsequence of the stringbanana
:banana
| |
an naSubstring
A substring (or factor) of a string T = t_1 dots t_n is a string hat T = t_{1+i} dots t_{m+i}, where 0 leq i and m + i leq n. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If hat T is a substring of T, it is also a
subsequence , which is a more general concept. Given a pattern P, you can find its occurrences in a string T with astring searching algorithm . Finding the longest string which is equal to a substring of two or more strings is known as thelongest common substring problem .Example: The string
ana
is equal to substrings (and subsequences) ofbanana
at two different offsets:banana
|||
ana|
|
anaIn the mathematical literature, substrings are also called subwords (in America) or factors (in Europe).
Prefix
A prefix of a string T = t_1 dots t_n is a string widehat T = t_1 dots t_{m}, where m leq n. A "proper prefix" of a string is not equal to the string itself and not empty
Wikimedia Foundation. 2010.