Subarray / Substring / Subsequence

SubsequencePermalink

Definition: Let $⟨x_n⟩$ be a sequence in a set $S$. Let $⟨n_r⟩$ be a strictly increasing sequence of indices in $\mathbb{N}$. Then the composition $⟨x_{n_r}⟩$ is called a subsequence of $⟨x_n⟩$.

• E.g., the prime numbers $\mathbb{P}$ are a subsequence of the natural numbers $\mathbb{N}$.

描述性的定义：a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

• E.g., $⟨A,C⟩$ could be a subsequence of $⟨A,B,C⟩$, but not a subarray

SubarrayPermalink

A subarray is a contiguous/consecutive subsequence of an array.

By contiguous/consecutive, 我觉得它的意思是 sequence of indices $⟨n_r⟩$ is a sequence of consecutive integers $⟨m,m+1,m+2,\dots ⟩$

SubstringPermalink

A substring is exactly the same thing as a subarray but in the context of strings.