Cha*_*ani 11 algorithm math combinations
对于长度为n的字符串,计算所有子字符串的公式为:n(n + 1)/ 2有人可以帮助我直观地理解这个公式吗？
维基百科说: "符号只出现一次的长度字符串的子串数是在符号之间选择两个不同位置以开始/结束子字符串的方式的数量"
小智 37
要理解这一点,请注意任何子字符串都需要两个参数:start index和end index.
例如:string str ="Hello World"; // length == 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子串.通过总结:
Sigma(n + 1 - i)从i = 1到n,得到的n * (n + 1) - n * (n + 1) / 2是n * (n + 1) / 2
嗯，它是所有长度为 1（正好为 n）的子串的总和，加上所有长度为 2 (n-1) 的子串，再加上所有长度为 n 的子串（这是一个真串）。然后，你有 n + n-1 + n-2 ... + 1 = (n * (n+1)) / 2
该和可以使用自然归纳法来计算，并且由于高斯在学校时解决了这个和而闻名。
子字符串由其在原始字符串中的开始和结束位置确定。对于任何子串，我们都有这两个端点。相反，对于字符串中的任何两个字符，只有一个子字符串在这些点处开始和结束。
因此，所有子字符串的数目是所有（不必是不同的）字符对的数目。
有n*(n-1)/2成对的不同字符。您还需要添加非区别对，即n。
因此总数为n * (n-1) / 2 + n = n * (n+1) / 2。