子串（substring）和子序列 （subsequence）的区别是什么？

之前没有细心理解过二者概念，今天自己来补一下这方面知识。

1 背景介绍

在做算法题的时候，经常会遇到子序列问题，如 Logest Increasing Subsequence 问题

如对于序列数组：[4 ,2, 4，5, 3, 7]

最长的递增子序列是 [2, 3, 4，7]

和之前学习到子串的定义感觉有所不同，但又说不上来什么不同。比较直观的理解就是，可以在原来数组中任意划掉一个或者多个元素，就可以构出子序列。

如划掉2； [4 ， 4，5, 3, 7] 也是子序列。

故笔者整理相关知识，以方便后来者借鉴学习。

2 子串-substring

关键词：

连续

子串定义：子串，计算机术语，串中任意个

连续的字符

组成的子序列称为该串的子串。

下面举几个例子：

ab的子串：a、b、ab、/0(空串）共4个即（2+1+1）个，

abc的子串：a、 b、 c、 ab、 bc 、abc、/0共（3+2+1+1）个，

所以若字符串的长度为n,


则子串的个数就是[n

(n+1)/2+1]个，

*

3 子序列-subsequence

关键词：

任意地选取

，即不用连续

1，子序列定义：

给定序列{Xn}，从中

任意地选取

无限项，按照原来的顺序组成的序列称为序列{Xn}的一个子序列。子序列是序列。通俗理解，序列就是在原来序列中找出一部分组成的序列。

2 子序列的其他定义：一个给定的序列的子序列是在该序列中删除若干元素后得到的序列。

下面举几个例子：

序列12356710它的子序列：

比如：12,13 ,15,16,1356,137,…

其他相关术语：

所谓的递增子序列: 首先它是子序列, 其次它们的元素是递增的,也就是说是原来原大的. 最长子序列就是子序列中元素的个数是最多的那一序列.

4 子串和子序列的相同点

当子序列连续取时，和子串定义方式类似。它们都是取原来数据的一部分来构成。

故子串一定是子序列，而子序列则不一定是子串。

5 子串和子序列的区别

由前面定义可以看出，子串是子序列的特例。子序列是在更大的一个范围。

笔者在下面画一个简单的Venn图，以方便理解：

子串的定义出现在数据结构里面，子序列的定义算法设计与分析这本书里面。

6 引用

[1] https://baike.baidu.com/item/%E5%AD%90%E4%B8%B2/11047664?fr=aladdin

[2] https://zhidao.baidu.com/question/752410941258002692.html