從如何確定一個子串是否是迴文串開始，我們需要知道這樣的 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 陣列的問題。為了節約輪子成本，求解過程請參考上述連結。

這就是馬拉車演算法啊！

public static void main(String[] args) {

String str = "asfasfnabaasdfnbassdnbasnbasdnbadfasdfnba";

String key = "nba";

int startindex = 0;

int count = 0;

while ((startindex = str.indexOf(key, startindex)) >= 0) {

count++;

System.out.println("位置：" + startindex);//可以提前宣告一個數組用來存放

startindex += key.length();

}

System.out.println("總數" + count);

}