c語言求一個字符串里有幾個子串？

從如何確定一個子串是否是回文串開始，我們需要知道這樣的 pair（中心，半徑）。意思是從每個中心點(diǎn)最多可以向左或者向右擴(kuò)展的半徑。因?yàn)榛匚拇L度可能是奇數(shù)或偶數(shù)，可以用一種技巧來消除這種特判，在相鄰字符中間插入一個特殊字符（如 ‘#’）。

例如，“12212321" => "#1#2#2#1#2#3#2#1#"，如果令 P[i] 為以第 i 個字符為中心的擴(kuò)展半徑，你會發(fā)現(xiàn)其對應(yīng)的最長回文串的長度就是 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 - 將所有歡脫傾翻）

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

這就是馬拉車算法?。?/p>