algorithm - 字符串中子串的个数 : n-squared or exponential

Question

一个字符串一般有多少个子串？

Why does string x [1:n] have O(n^2) subtrings according to the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why it is not O(2^n)?

这是一个链接 [http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec21。 pdf]

Answer 1

取一个字符串长度n=4，比如说:“ABCD”

以上的子串(按长度):

• 1个字符:A,B,C,D(4子串)
• 2个字符:AB,BC,CD, (3子串)
• 3个字符:ABC,BCD(2子串)
• 4个字符:ABCD(1子串)

将数字相加得出:1+2+3+4 = 10。

所以，概括地说，可能的子字符串的数量是从 1 到 n 的所有整数的总和。

此总和是使用公式 (n^2 + n)/2 计算得出的(参见此处:Sum of Consecutive Numbers)

所以效率是n^2数量级。