algorithm - 查找字符串的子字符串

Question

对于长度为 n 的字符串，计算所有子字符串的公式是：n(n+1)/2 有人可以帮我直观地理解这个公式吗？

维基百科说： “符号仅出现一次的长度字符串的子字符串数，是在符号之间选择两个不同位置以开始/结束子字符串的方式的数量”

score 64 · Accepted Answer

要理解这一点，请注意任何子字符串都需要两个参数：开始索引和结束索引。

例如：string str = "Hello World"; // 长度 == 11

让我们从一次只取一个字符的子字符串开始：H, e, l, l, o, , W, o, r, l, d。然后每次取 2 个字符：He、el、ll、lo、o、W、Wo 或 rl、ld。然后取 3 个字符：Hel，.. 等。

所以总的子串数是 11 + 10 + 9 + .. + 1 并且，一般来说for i from 1 to n，我们有n - i + 1子串。通过峰会：

从 i = 1 到 n 的 Sigma (n + 1 - i)，n * (n + 1) - n * (n + 1) / 2产生n * (n + 1) / 2

score 8 · Accepted Answer

子字符串由它在原始字符串中的开始位置和结束位置确定。对于任何子串，我们都有这两个端点。相反，对于字符串中的任何两个字符，只有一个子字符串在这些点开始和结束。

因此，所有子串的数量是所有（不一定是不同的）字符对的数量。

有n*(n-1)/2成对的不同字符。您还需要添加非不同对，即 n。

所以总数为n * (n-1) / 2 + n = n * (n+1) / 2。

score 6 · Accepted Answer

嗯，它是所有长度为 1（正好是 n）的子串，加上所有长度为 2（n-1）的子串，加上所有长度为 n（这是一个正确的字符串）的子串的总和。然后，你有 n + n-1 + n-2 ... + 1 = (n * (n+1)) / 2

总和可以使用自然归纳法计算，并且由于高斯在学校时解决了这个总和而为人所知。

score 4 · Accepted Answer

子字符串由它的两个端点定义，基本上我们可以将子字符串视为字符串的切片。让我们通过一个例子来理解它。考虑长度为 3 的字符串“abc”

美国广播公司

要对字符串进行切片，我们有 4 个位置，从 a 之前到 c 之后的字符串结尾。从这 4 个可用选项中，我们必须选择 2 个位置来创建切片，即等于⁴ C ₂ == ⁿ⁺¹的子字符串C ₂ ==n*(n+1)/2

score 1 · Accepted Answer

我不擅长数学，但是什么是substrings字符串以及获得字符串的可能性是什么，substrings我将尝试向您解释。

举个例子：“MOBILE”这是一个 6 个字符的字符串，现在根据你的公式 n(n+1)/2，结果是 6(6+1)/2=21

因此，子字符串是在整个字符串之间具有起始索引和结束索引的任何字符串。

在字符串“MOBILE”中，以下是我们可以拥有的子字符串：

第 1 步：“M”开始索引“M”和结束索引“M”这是一种可能性

第 2 步：“MO”开始索引“M”和结束索引“O”这是第二种可能性

.

第 5 步：“MOBIL”开始索引“M”和结束索引“L”这是第五种可能性

.

第 8 步：“OB”开始索引“O”和结束索引“B”这是八种可能性

.

第 21 步：“MOBILE”开始索引“E”和结束索引“E”这是第 21 种可能性

这些是在字符串中包含子字符串的可能性，并且子字符串中的结束索引不能小于开始索引。

score 1 · Accepted Answer

假设你想找出 "abc" 的子串，那就是 {"a","ab","abc","b","bc","c"} 我们将通过以下代码计算它

for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){

        }
    }

查看这段代码，很容易看出循环运行为

第一次运行3次，第二次运行2次，第三次运行1次

由于它每次都返回一个子字符串，因此它等于 n 的总和， 即 = n(n + 1) / 2

6 回答 6