第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”。