查找字符串的子串

Question

对于长度为n的字符串，计算所有子串的公式为：n(n+1)/2。

有人能帮我直观地理解一下这个公式吗？

维基百科上说："长度为n且符号仅出现一次的字符串的子串数量，是选择两个不同位置作为子串起始或结束位置的方式数目。"

- Chander Shivdasani

---

请查看此链接，了解有关公式n(n+1)/2的另一些信息：http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/runsums/triNbProof.html - kermit

Answer 1

为了理解这个问题，需要注意任何子字符串都需要两个参数：起始索引和结束索引。

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

让我们从一次只取一个字符的子字符串开始：H、e、l、l、o、空格、W、o、r、l、d。然后再取两个字符：He、el、ll、lo、o、W、Wo、or、rl、ld。接着取三个字符：Hel，等等。

因此，总的子字符串数量是11 + 10 + 9 + ... + 1，通常情况下，对于i从1到n，我们有n - i + 1个子字符串。通过求和：

Sigma (n + 1 - i) from i = 1 to n，得到n * (n + 1) - n * (n + 1) / 2，即n * (n + 1) / 2。

- user586399

---

仍不清楚如何从 i=1 到 n 的 Sigma (n + 1 - i) 获取 n * (n + 1) - n * (n + 1) / 2 - Maxim Palenov

Answer 2

一个子串由原始字符串的起点和终点确定。对于任何子串，我们都有这两个端点。反过来，对于字符串中的任意两个字符，恰好有一个子串从这些点开始并在这些点结束。

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

有n *（n-1）/ 2 个不同字符对。您还需要添加非不同对，即为n个。

所以总数是n *（n + 1）/ 2 。

- Petar Ivanov

Answer 3

嗯，它是所有长度为1的子字符串（恰好为n）的总和，再加上所有长度为2的子字符串（n-1），再加上所有长度为n的子字符串（即正确的字符串）。然后，您有n + n-1 + n-2 ... + 1 =（n *（n + 1））/ 2。

可以使用自然归纳法计算总和，这也是由高斯在他上学时解决的问题。

- Luixv

---

你的意思是 n*(n+1)/2 吗？ - madCode

Answer 4

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

a b c

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

- Lupin

Answer 5

假设你想找到字符串"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

- Aditya

Answer 6

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

让我们举个例子：“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”，这是第二十一种可能性。

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

- FosterZ