“Let’s go”
基本概念
subarray
A subarray is a slice from the array which is contiguous (i.e. occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of the array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
substring
A substring of a string S is a string S’ that occurs in S. A substring is almost similar to a subarray but it is in context of strings.
For example, the substrings of the string ‘apple’ are ‘apple’, ‘appl’, ‘pple’, ‘app’, ‘ppl’, ‘ple’, ‘ap’, ‘pp’, ‘pl’, ‘le’, ‘a’, ‘p’, ‘l’, ‘e’, and ‘’. Below is C++ and Java program that generates all non-empty substrings of the specified string:
subsequence
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, {A, B, D} is a subsequence of sequence {A, B, C, D, E} that is obtained after removing {C} and {E}.
People are often confused between a subarray and a subsequence. A subarray will always be contiguous but a subsequence need not be contiguous. That is, unlike subarrays, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequence and subarray are same.
In other words, the subsequence is a generalization of substring or substring is a refinement of the subsequence. For example, {A, C, E} is a subsequence of {A, B, C, D, E}, but not a substring and {A, B, C} is both a subarray and a subsequence.
Please note that a Subsequence can be in context of both arrays and strings. Generating all subsequences of an array/string is equivalent to generating power set of the array/string. For a given set S, the power set can be found by generating all binary numbers between 0 to 2n-1 where n is the size of the given set. This is demonstrated below:
subset
A subset is any possible combination of the original set. The term subset is often used for subsequence but this is wrong. A subsequence always maintain the relative order of elements of the array (i.e. increasing index) but there is no such restriction on a subset. For example, {3, 1} is a valid subset of {1, 2, 3, 4, 5} but it is neither a subsequence or a subarray.
It is worth noting that all subarrays are subsequences and all subsequences are subset but the reverse is not true. For instance, the subarray {1, 2} of the array {1, 2, 3, 4, 5} is also a subsequence and a subset.
