※ 引述《anoymouse (没有暱称)》之铭言：
:
:
先澄清变量，n是主串长度，m是要找的子串长度，问题应该是我们要从主串里面
找到子串吧。
: 1.请教为什么"googlegood"字串搜寻"google"是 O(1)?
: 就算第一个位置就是了，循环还是要跑google这个字串长度的次数才有找到吧?
如你所说，应该是m次 -> O(m)。
: 2. "abcdefgoogle" 为什么又是O(m + n)? 循环abcdef都走else，碰到'g'开始走if
: 不是else部分( m - n) 次 + if部分 n 次 = m次 ?
同样如你所说，应该是n次 -> O(n)。
: 机率原则为什么是(m+n)/2?
等机率原则是这么思考的：
所谓的最佳情况，就是没走到岔路的所有情况。也就是说同样n长度的主串与同
样长度m的子串而言：
[长度0] [长度m] [长度n-m]
google abcdef -> O(m)
[长度1] [长度m] [长度n-(m+1)]
a google bcdef
.
.
[长度(n-m)] [长度m] [长度0]
abcdef google -> O(n)
每一个情况的发生机率是相等的。所以把最佳情况跟最差情况相加除以二（平均
）会等同于所有情况的平均（梯形取中间宽度的意思）。
所以其实他结论算是没错，(n + m)/2 -> O(n+m)。但是他是用(1+(n+m))/2凑出
来刚好赛中O(n+m)的XD