为什么一个字符串的可能子串总数是n^2？

Question

我读到一个给定字符串可以形成的子字符串总数是 n^2，但我不知道如何计算它。

关于子字符串，我的意思是，给定一个字符串 CAT，子字符串将是：

C
CA
CAT
A
AT
T

Answer 1

你有一个起点和一个终点 - 如果每个点都可以指向单词的任何地方，每个点都有 n 个可能的值，因此总共有 n^2，所以这是一个上限。

但是，我们需要一个约束来说明子字符串不能在开始之前就结束，所以 end - start >=0。这将可能的计数减少了大约一半，但在渐近条件下它仍然是 O(n^2)

Answer 2

子串计算符合逻辑

selecting 2 blank spaces atleast one letter apart.

a| b c | d = substring bc
| a b c |d = substring abc.

Now how many ways can you chose these 2 blankspace. For n letter word there are n+1.

Then first select one = n+1 ways
Select another (not the same)= n
So total n(n+1). But you have calculated everything twice. So n*(n+1)/2.


Programmatically, without applying any special algorithms(like Z algo etc) you can use a map to calculate no of distinct substrings.(O(n^3)).

您可以使用后缀树来获得 O(n^2) 子串计算。

Answer 3

（非空）子字符串总数为 n + C(n,2)。前导n统计长度为1的子串个数，C(n,2)统计长度>1的子串个数，等于从[=11=的集合中选择2个索引的方式数].二项式系数的标准公式得出 C(n,2) = n*(n-1)/2。结合这两项并简化得出总数为 (n^2 + n)/2。评论中的 @rici 指出这与 C(n+1,2) 相同，如果您例如考虑 Python 字符串切片，其中 s 的子字符串总是可以写成 s[i:j] 的形式，其中 0 <= i < j <= n （j 比最终的多 1指数）。 n = 3 的结果是 (9 + 3)/2 = 6。

在复杂性理论的意义上，子串的数量是 O(n^2)，这可能是你在某处读到的。

Answer 4

要获取给定字符串 s 的子字符串，您只需 select 字符串中的两个不同点。让s包含n个字符，

|s[0]|s[1]|...|s[n-1]|

你想选择两个vertical bars得到一个子串。你有多少vertical bars？正是 n+1。所以sustrings的个数为C(n+1,2) = n(n+1)/2，也就是从n+1中选择2项。当然也可以写成O(n^2)。

为什么一个字符串的可能子串总数是n^2？

Why is the total number of possible substrings of a string n^2?

algorithm

counting