A subsequence, substring, prefix or suffix of a string is a new string, containing elements from the original, and in the same order. In this context, the terms string and sequence have the same meaning. In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... In mathematics, a sequence is a list of objects (or events) arranged in a linear fashion, such that the order of the members is well defined and significant. ...

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 a subsequence of two or more strings is known as the longest common subsequence problem. In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. ...

Substring

A substring of a string is a string . A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If P 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 a string searching algorithm. Finding the longest string which is a substring of two or more strings is known as the longest common substring problem. In mathematics, a subsequence of some sequence is a new sequence which is formed from the original sequence by deleting some of the elements without disturbing the relative positions of the remaining elements. ... String searching algorithms are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. ... The longest common substring problem is to find the longest string(s) that is a substring of two or more strings. ...

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^[1] (0 < m < n). A prefix can be seen as a special case of a substring.

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^[2] (0 < m < n). A suffix can be seen as a special case of a substring.

Examples

The string anna is a subsequence of the string banana:

 T = banana || || P = an na 

The string ana is a substring (and subsequence) of banana at two different offsets:

 T = banana ||||| P = ana|| ||| P = ana 

The string ban is a prefix (and substring and subsequence) of the string banana:

 T = banana ||| P = ban 

The string nana is a suffix (and substring and subsequence) of the string banana:

 T = banana |||| P = nana 

References

• ↑ Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.