如何證明Manacher演算法的時間複雜度是O(n)?

01-01

就是求最長迴文子串的那個演算法

謝邀：

我希望：題主事先已經知道了Manacher這個演算法，以及該演算法的細節，以及能看得懂這個鏈接裡面的介紹hdu3068之manacher演算法+詳解，如果不能做到以上幾點，那麼我沒什麼好講的。

然後我結合鏈接裡面的內容講一下時間複雜度。

如果我們能證明maxlen或i+k的每增加1隻需要有限個單位的時間，而當maxlen增加到2n+1時這個演算法也就結束了，或者當i+k=2N+1時這個演算法也就結束了。

大概如上圖所示，那個黑線的右邊已經到頂了。。。右邊紅線的長度一定會大於右邊藍線的長度，也就是沒有必要迭代了，不可能找到更長得迴文串了。。或者i+k到了n該演算法自然結束。。。T（N）&<2(N+1)+ 2（N+1） = O(N) 即可得證

現在

我們現在證明maxlen或i+k的每增加1隻需要有限個單位的時間

如下圖

如果是1這種情況，明顯我們每次執行while就能夠讓maxlen+1，執行完i+k會+1

如果是2，那麼分成三種情況

第一種.單位時間，讓i+k向右移動一下，（那個橙色不可能超過黑色線右端，一旦超過，黑色線就得重畫，而橙色線本身可以到達黑色線右端，所以直接就是結果，也就是即使寫了while也必定會在第一次循環）

第二種.單位時間讓i+k向右移動一下，（如果右邊的藍色線能擴展，那麼對稱過來的左邊的藍色線也能擴展了，而左邊的我們已經計算出來沒法擴展了，所有，右邊的藍色線就是界限，即使寫了while也必定在第一次循環退出）

第三種情況，每次執行以下while，那麼就會讓maxlen向右移動一下。。。while結束後i+k移動一下

所以綜合以上有所情況，每個單位運算要麼讓maxlen向右移動一下，要麼讓i+k向右移動一下。而i+k&<2N+1,且maxlen&<2N+1，所以，整個演算法的運行時間一定小於2N+1 + 2N+1 = O(N)

當然這個證明可以用勢能法單純以maxlen為標準做勢能法。過程我就不講了。其實和上面分析類似。

核心代碼

void manacher(char* s) { int c = 0, r = 0; p[0] = 0; for( int i = 1; s[i]!="" ; ++i ) { if( r &> i ) p[i] = min( p[ 2 * c - i ], r - i ); else p[i] = 0; while( s[i + 1 + p[i]] == s[i - 1 - p[i]] ) p[i]++; if( i + p[i] &> r ) { r = i + p[i]; c = i; } } }

演算法複雜度

從代碼可以看出。

manacher演算法只需要線性掃描一遍預處理後的字元串。

對 $p[]$ 數組的處理 $i$ 為 $i$ 關於 $c$ 的對稱點

1. 在 $i < r$ 的情況下，p的值可以在 $O(1)$ 時間內確定

2. 在 $i>r<br />$ 的情況下，p的值需要 $O(n)$ 的時間內確定，但是在情況2下，每次掃描都從 $r+1$ 開始，且 $r$ 自身的變化情況是單調遞增的，這樣可以保證，字元串中的每個字元最多被訪問2次，所以，該演算法的時間複雜度是線性 $O(n)$

只需要弄清楚兩點

while()循環本身的時間複雜度在沒有前提條件的情況下確實是 $O(n)$
但是這裡的 $r$ （也就是上面答案中的 $maxlen$ ），是不斷往後走而不可能往前退的，它自身的值的變化是遞增的。那麼你可以明白，要進入while循環， $i$ 的值必然是比 $r$ 大的，也就是說整個程序結束為止，while循環執行的操作數為 $n$ 次（線性次），而字元串中的每個字元，最多能被訪問到2次。時間複雜度必然為 $O(n)$

兩個指針必然有一個至少挪動一位，而且消耗時間和位移動成正比，而且不會向左移。

剛想了想，整理了下思路，不知道對不對。

比較次數的多少是和 $max$ （迴文最右邊位置）有關的，也就是說複雜度是和 $max$ 從 $0$ 位置移動到 $n-1$ 的位置次數是線性相關的， $max$ 從 $0$ 移動到 $n-1$ 位置最多為 $O(n)$ 次，因此演算法的時間複雜度是 $O(n)$ 。

--------------------------------------------------------------------------------------------------------------------------

下面嘗試下證明。

設比較第 $i$ 個字元時比較次數為 $f(i)$ ，此時 $max$ 的位置記為 $left( max ight)_{i-1}$ (上一次比較後 $max$ 的位置)。比較完成後 $max$ 的位置記為 $left( max ight)_{i}$ 。

$f(i)=left( max ight)_{i}-i$ $(i>left( max<br /> ight)_{i-1})$

$f(i)=left( max ight)_{i}-left( max ight)_{i-1}$ $or$ $0$ $(ileqleft( max ight)_{i-1})$

總比較次數 $f=sum_{0}^{n-1}{f(i)}leqsum_{0}^{n-1}{(max)_{i}}-{(max)_{i-1}}leq n$

所以Manacher演算法的複雜度是嚴格 $O(n)$ 的。

for(int i = 1; i &< n - 1; i++) { j = 2*id - i; if(maxLen &> i) p[i] = std::min(maxLen - i + 1, p[j]); else p[i] = 1; while (i-p[i] &>=0 i + p[i] &< n mStr[i + p[i]] == mStr[i - p[i]]) p[i]++; //計算id及maxLen if (i + p[i] &> maxLen) { maxLen = i + p[i] - 1; id = i; } }

@白榮東我想，樓主想問的是為什麼下面這個循環的時間複雜度與n無關。

如果按照直覺，這個循環可能與n有關。

while (i-p[i] &>=0 i + p[i] &< n mStr[i + p[i]] == mStr[i - p[i]]) p[i]++;