判斷最長回文串——暴力、延展、Manacher

1. 暴力

時間複雜度O(n^3)。

2. 延展

 以某一字元為中心，設定left, right兩個變量同時向外擴，判斷他們指向字元是否相同。注意分奇偶讨論。時間複雜度O(n^2)。

3. Manacher 馬拉車

 代碼注釋：

1 const int MAXN = 110009;
 2 char ma[MAXN * 2];   //因為要添加'#',是以長度要開兩倍
 3 int mp[MAXN * 2];
 4 char s[MAXN];
 5 
 6 void Manacher(char s[], int len) {
 7     
 8     // 1. 構造字元串,添加'#',使長度變為奇數(2 * len - 1)
 9     int l = 0;
10     ma[l++] = '$';   // 設定邊界
11     ma[l++] = '#';
12     for(int i = 0; i < len; i ++) {
13         ma[l++] = s[i];
14         ma[l++] = '#';
15     }
16     ma[l] = 0;
17     
18     // 核心: 求回文半徑, 回文半徑包括中心點
19     int mx = 0; // mx代表可達的最右值
20     int id = 0; // id代表mx的中心  
21     for(int i = 0; i < l; i ++) {
22         mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
23         while(ma[i + mp[i]] == ma[i - mp[i]]) {
24             mp[i] ++;
25         }
26         if(i + mp[i] > mx) {
27             mx = i + mp[i];
28             id = i;
29         }
30     }
31 
32 }
33 
34 int main()
35 {
36 
37     while(scanf("%s", s) != EOF) {
38         int len = strlen(s);
39         Manacher(s, len);
40         int ans = 0;
41         for(int i = 0; i < 2 * len + 2; i ++) {   // 尋找最長的回文半徑，即回文串長度
42             ans = max(ans, mp[i] - 1);  // 回文半徑減1就是原回文串的長度(回文半徑中虛加了#)
43             cout << mp[i] << " ";
44         }
45         printf("%d\n", ans);
46     }
47 
48     return 0;
49 }      

時間複雜度O(n)。