|
A subsequence, substring, prefix or suffix of a string is 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 is a string such that , where . 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 string banana:banana || || an na Substring A substring of a string is a string , where and . A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If is a substring of , it is also a subsequence, which is a more general concept. Given a pattern , you can find its occurrences in a string 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. Example: The string ana is a equal to substrings (and subsequences) of banana at two different offsets:banana ||||| ana|| ||| ana In the mathematical literature, substrings are also called subwords (in America) or factors (in Europe). Prefix A prefix of a string is a string , where . A proper prefix of a string is not equal to the string itself and not empty (). A prefix can be seen as a special case of a substring. Example: The string ban is equal to a prefix (and substring and subsequence) of the string banana:banana ||| ban Suffix A suffix of a string is a string , where . A proper suffix of a string is not equal to the string itself and not empty (). A suffix can be seen as a special case of a substring. Example: The string nana is equal to a suffix (and substring and subsequence) of the string banana:banana |||| nana | ||||||||
|
| |||||||||
 |
|
| |