如何求兩個任意長度字符串中的最長匹配子串？

從如何確定一個子串是否是回文串開始，我們需要知道這樣的 pair（中心，半徑）。意思是從每個中心點最多可以向左或者向右擴展的半徑。因為回文串長度可能是奇數或偶數，可以用一種技巧來消除這種特判，在相鄰字符中間插入一個特殊字符（如 ‘#’）。

例如，“12212321" => "#1#2#2#1#2#3#2#1#"，如果令 P[i] 為以第 i 個字符為中心的擴展半徑，你會發現其對應的最長回文串的長度就是 P[i] - 1。

S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1 (p.s. 可以看出，P[i]-1正好是原字符串中回文串的總長度）

（參考自：O(n)時間求字符串的最長回文子串 - Felix021 - 將所有歡脫傾翻O(n)時間求字符串的最長回文子串 - Felix021 - 將所有歡脫傾翻）

所以就歸結到如何求 P 數組的問題。為了節約輪子成本，求解過程請參考上述鏈接。

這就是馬拉車算法啊！