一个字符串有多少个子串

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

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

Answer 2

取一个字符串长度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个数量级。

Answer 3

给定一串n个元素，

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

如果从第2个元素开始，你可以形成n-1个字符串....所以......

例如，取1234

1,12,123,1234

2,23,234

3,34

4

如你所见，总数是n + (n-1) + (n-2) ...1，即n个元素的总和，即n(n+1)/2

Answer 4

你可能会对一组子集的数量感到困惑，但这里似乎很重要的是这些是具有固定模式的子串和你认为2 ^ n的值，即给定字符串的子序列数。

Answer 5

您想要获得的子串数量一样多。从索引开始和结束。

string.Substring(0, 10); // untill 10th character, and so on

http://msdn.microsoft.com/en-us/library/aka44szs(v=vs.110).aspx

如果您正在尝试使用foreach获取字符串，您将获得在空格字符处分割的每个字符串。因此，空格字符将指定字符串内的字符串数。

string strngs = "Love for all, Hatred for none!";

foreach (string strng in strngs) {
   Console.WriteLine(strng);
}

// (Expected) Output
// Love
// for
// all,
// Hatred
// for
// none!