一个字符串有多少个子串

Question

字符串中有多少个子字符串？

Why does string x [1:n] have O(n^2) subtrings in the lecture 21 Dynamic Programming III of        
6.006 from MIT? 
Why 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计算此总和(参见此处:连续数字的总和)

因此效率为n ^ 2个数量级.

Answer 2

简单地,子字符串由两个参数定义,这两个参数[i,j]是原始字符串中子字符串的起始索引和结束索引.现在,0<=i,j<=n作为指标应该是字符串内,总价值i&j每个人都可以有n个这样的所有组合[i,j]将n*n是O(n^2)

Answer 3

给定一串n个元素，

如果从第一个元素开始，则可以形成n个字符串

如果从第二个元素开始，则可以形成n-1个字符串..依此类推...

例如，取1234

1,12,123,1234

2,23,234

3,34

4

正如你所看到的，一共是n + (n-1) + (n-2) ...1即n个元素的总和是n(n+1)/2