Substring - Subsequence

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:

Including the empty subsequence, the number of subsequences of a string of length where symbols only occur once, is simply the number of subsets of the symbols indices, i.e. .