最長迴文子字串

最長迴文子字串 The longest palindrome

(強烈建議閱讀本文之前先閱讀演算法筆記中的Longest Palindromic Substring會比較好懂)

Manacher's ALGORITHM: O(n)時間求字串的最長回文子串
這個演算法簡單來說就是：利用鏡射原理(因為回文為對稱字串，故中心點字母的左邊右邊會長一樣)

想法1：輸入一字串，如 aabba，我們以各個字母為中心向左向右延伸就可以找到最長迴文，但很費時。如以第一個a為中心、發現最常迴文就是自己(length=1)、再以第二個字母a為中心，以此類推...

想法2：有沒有方法可以省時一點呢？我們以每個字母為中心的算法，是否會計算到重覆的子字串？
設 p[i]為以 i 字母為中心的最長字串，計算 p[i] ，是運用已經算好的 p[id] ， id < i 。也就是指某一段已經算好的 s[id ... id-p[id]+1] = s[id ... id+p[id]-1] 。首先找出有覆蓋到 s[i] 的 s[id ... id+p[id]-1] 是那一段，而且 id+p[id]-1 越右邊越好。
 (id為已知右邊界最大的中心，mx為右邊界的index)

於是，我們可以發現一個規則，分為兩種情況：

(1) 當 mx - i > P[j] 的時候，以S[j]為中心的回文子串包含在以S[id]為中心的回文子串中，由於 i 和 j 對稱，以S[i]為中心的回文子串必然包含在以S[id]為中心的回文子串中，所以必有 P[i] = P[j]，見下圖。

(2) 當 P[j] >= mx - i 的時候，以S[j]為中心的回文子串不一定完全包含於以S[id]為中心的回文子串中，但是基於對稱性可知，下圖中兩個綠框所包圍的部分是相同的，也就是說以S[i]為中心的回文子串，其向右至少會擴張到mx的位置，也就是說 P[i] >= mx - i。至於mx之後的部分是否對稱，就只能老老實實去匹配了。

對於 mx <= i 的情況，無法對 P[i]做更多的假設，只能P[i] = 1，然後再去匹配了。

AC代碼如下：(題目來源：http://hihocoder.com/problemset/problem/1032)

 1  #include <stdio.h>

 2  #include <stdlib.h>

 3  #include <iostream>

 4  #include <algorithm>

 5  #include <string>

 6  #include <string.h>

 7  using namespace std;

 8  int p[2000010]= {0};

 9  int longest_palindrome(string str)

10  {

11 

12      ///insert special char

13 

14      int len=str.length(),nlen=len*2+1,c=0,ans=0;

15      string s;

16      char tmps[2000010]="";

17      memset(tmps,'.',nlen);

18      s = tmps;

19      for(int i=1; i<nlen; i+=2) s[i]=str[c++];

20 

21 

22      ///matching

23 

24      int center=0,right=0;

25      for(int i=1; s[i]!='\0'; i++)

26      {

27          p[i]= right > i ? min(p[2*center-i],right-i) : 1; 

             //右邊界是否包含i(有包含的話就比較p[對稱點]跟right-i的長度選小的)

28          while(i-p[i] >= 0 && i+p[i] < nlen && s[i+p[i]]==s[i-p[i]]) p[i]++;

29          if(i+p[i] > right)

30          {

31              right=i+p[i];

32              center=i;

33          }

34          ans = max(p[i],ans);

35      }

36      return ans-1;

37  }

38  int main()

39  {

40      int test;

41      cin >> test;

42      while(test--)

43      {

44          string str;

45          cin >> str;

46          cout << longest_palindrome(str) << endl;

47      }

48      return 0;

49  }

參考文獻：
1. https://www.felix021.com/blog/read.php?2040
2. http://www.csie.ntnu.edu.tw/~u91029/Palindrome.html#3