第2章 字符串

2.1 字符串与子串、子序列

字符串是由零个或多个字符组成的有限串行。

子串的定义是：串中任意个连续的字符组成的子序列，并规定空串是任意串的子串，任意串是其自身的子串。对于一个字符串变量，例如"adereegfbw", 它的子串就是像"ader"这样可以从中找到的连续的字符串。字符串"adereegfbw"本身及空串也属于它本身的子串，其中字符串本身是它的最长子串。

例1：字符串“www.qq.com”所有非空子串个数为（如果两个子串相同则算一个）。（2012·腾讯）

A.1024

B.1018

C.55

D.50

解答：D。长度为1的子串有10个，减去重复的2（子串w重复）+1（子串q重复）+1（子串.重复）=4个，还剩6个，长度为2的子串有9-1（子串ww重复）=8个，长度为3的子串有8个，长度4有7个……长度为10的子串有1个，加起来为50。

子序列则不要求字符连续，但顺序与其在主串中相一致，即若有“abcd”与“ad”，则两者的最长公共子序列是“ad”。