数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
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)。
正文完