※ 引述《anoymouse (沒有暱稱)》之銘言：
: https://imgur.com/O5P83PO
: https://imgur.com/Pz3PwRP
先澄清變數，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