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.

Subsequence

Main article subsequence

A subsequence of a string $T\; =\; t\_1\; t\_2\; \backslash dots\; t\_n$ is a string $P\; =\; p\_1\; \backslash dots\; p\_m\; =\; t\_\{i\_1\}\; \backslash dots\; t\_\{i\_m\}$ such that , where $m\; \backslash leq\; n$. 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.

Example: The string anna is a subsequence of the string banana:

T = banana || || P = an na

Substring

A substring of a string $T\; =\; t\_1\; \backslash dots\; t\_n$ is a string $P\; =\; p\_1\; \backslash dots\; p\_m\; =\; t\_\{1+i\}\; \backslash dots\; t\_\{m+i\}$. 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.

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

T = banana ||||| P = ana|| ||| P = 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\; \backslash dots\; t\_n$ is a string $P\; =\; p\_1\; \backslash dots\; p\_m\; =\; t\_1\; \backslash dots\; t\_\{m\}$, where $m\; \backslash leq\; n$. 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 a prefix (and substring and subsequence) of the string banana:

T = banana ||| P = ban

Suffix

A suffix of a string $T\; =\; t\_1\; \backslash dots\; t\_n$ is a string $P\; =\; p\_1\; \backslash dots\; p\_m\; =\; t\_\{n-m+1\}\; \backslash dots\; t\_\{n\}$, where $m\; \backslash leq\; n$. 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 a suffix (and substring and subsequence) of the string banana:

T = banana |||| P = nana

References

Algorithms on strings

Подстрока