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 , 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 string banana:

banana
| |
an na

Substring

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 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 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 $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