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

我读到可以从给定字符串形成的子串的总数是n ^ 2,但我不明白如何计算它.

通过子串,我的意思是,给定一个字符串CAT,子串将是:

C
CA
CAT
A
AT
T

John Coleman.. 5

(非空)子串的总数是n + C(n,2).前导n计数长度为1的子串数,并C(n,2)计算长度> 1的子串数,并且等于从该组中选择2个索引的方式数n.二项式系数的标准公式得出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),这可能是你所读的地方.

(非空)子串的总数是n + C(n,2).前导n计数长度为1的子串数,并C(n,2)计算长度> 1的子串数,并且等于从该组中选择2个索引的方式数n.二项式系数的标准公式得出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),这可能是你所读的地方.