在判斷一個大字串 Text (T[1...n]) 裡面是否有出現小字串 Pattern (P[1...m]) 的時候，就是需要使用字串匹配演算法的時間了。（或者是使用現成的函式庫，比較安全安心效率有保障）今天來跟大家介紹 KMP 演算法～

KMP

KMP 演算法是 Knuth-Morris-Pratt 演算法的簡稱。他的精隨是利用動態規劃來找出 P 出現在 T 的所有位置。我們可以先預處理 P，建立一個 next() 陣列，其中 next(i) 表示，當我們比對 P[1], ..., P[i] 的時候，如果想比對下一個 P[i+1] 的時候發現比對失敗了，那整個 Pattern 應該要往右邊移動多少。

因此：next(i) 可以定義為 P 最長的前綴使得 P[1], ..., P[next(i)] = P[i-next(i)+1], ..., P[i] 而且 next(i) < i。要怎麼進行狀態轉移呢？我們注意到，計算 next(i+1) 的時候，可以利用已知的 next(i) 結果，檢查看看是否 P[next(i)+1] = P[i+1]。如果是的話，根據 next(i) 的定義我們知道它已經是最長的前綴，不可能有更長的了。所以此時 next(i+1) = next(i) + 1。

如果不是的話呢？我們就應該要檢查看看 next(next(i))+1，以此類推...

Exercise 39: Leetcode 214 - Shortest Palindrome

題目連結

https://leetcode.com/problems/shortest-palindrome/

題目敘述

給你一個字串 S，請在該字串前面加上最少數量的字元，使得整個字串變成回文字。

解題思考

其實這題就是問說 S 最長的迴文前綴可以有多長。換句話說呢，我們可以拿 S 去比對反過來的字串 rev(S)，看看什麼時候可以比對到結尾。第一次比對到結尾的時候，就代表最長的 rev(S) 後綴與 S 前綴相同，我們就得到最長的迴文前綴了。

參考程式碼 (Python3)

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        nxt = [-1] * len(s)
        for i in range(1, len(s)):
            j = -1
            if nxt[i-1] != -1:
                j = nxt[i-1]
                while j >= 0 and s[j+1] != s[i]:
                    j = nxt[j]
            nxt[i] = j + 1 if s[j+1] == s[i] else -1

        rev_S = s[::-1]
        now = 0
        for ch in rev_S:
            while now > 0 and ch != s[now]:
                now = nxt[now-1] + 1
            if ch == s[now]:
                now += 1
        return s[now:][::-1] + s

當然，這個方法只是本題眾多解法之一。一道好的面試題，必須要能夠有三種以上的解法，大家有興趣可以想想看有沒有更多種不同的作法～