数据结构 | 每日一练（106）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．名词解释：串

2．描述以下概念的区别：空格串与空串。

3．两个字符串 S1 和 S2 的长度分别为 m 和 n。求这两个字符串最大共同子串算法的时间复杂度为 T(m,n)。估算最优的 T(m,n)，并简要说明理由。

正确答案

PS：||代表注释

１．串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。

２．空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。

３．最优的T(m,n)是O（n）。串S2是串S1的子串，且在S1中的位置是1。开始求出最大公共子串的长度恰是串S2的长度，一般情况下，T(m,n) =O(m*n)。