manacher算法處理最長的回文子串（二），

manacher算法處理最長的回文子串（二），

      在上篇《manacher算法處理最長的回文子串（一）》解釋了manacher算法的原理，接著給該算法，該程序在leetcode的最長回文子串中通過。首先manacher算法維護3個變量。一個名為radius[i]的數組，表示以i為中心軸承的回文子串的半徑,如abcdcba中，字符d的下標為4，則他的radius[4]=3,下標的為0的a的半徑為radius[0]=0,即中心軸不考慮其中。一個idx表示上一次以idx為中心軸的回文。如果當以i為中心的回文在以idx為中心的回文內。則idx不更新，否則處理完radius[i]後，需要把idx更新為i。最後一個rad維護idx能夠包含最大的范圍的下一個字符下標，事實上當i+radius[i]到到達rad時就需要更新idx。

代碼：

 1 class Solution {
 2 public:
 3     string longestPalindrome(string s) {
 4         int n=s.size();
 5         string str(2*n+1,'0');
 6         bool flag=1;
 7         int j=0;
 8         int maxIdx=0;
 9         for(int i=0;i<2*n+1;i++){
10            if(flag){
11                str[i]='#';
12                flag=false;
13            }else{
14                str[i]=s[j++];
15                flag=true;
16            }
17         }
18         vector<int> radius(2*n+1,0);
19         int idx=0;
20         int rad=1;
21         for(int i=1;i<2*n+1;i++){
22             if(i>=rad){
23                 forceExtend(str,radius,idx,rad,i);
24                 maxIdx=(radius[i]>radius[maxIdx]?i:maxIdx);
25             }else if(i<rad){
26                 int j=2*idx-i;
27                 int idx_radius=idx-radius[idx];
28                 int j_radius=j-radius[j];
29                 if(j_radius>idx_radius){
30                     radius[i]=radius[j];
31                 }
32                 else if(j_radius<idx_radius){
33                     radius[i]=idx+radius[idx]-i;
34                 }else{
35                     radius[i]=idx+radius[idx]-i;
36                     int count=1;
37                     while((i+radius[i]+count)<=str.size()&&(i-radius[i]-count)>=0&&str[i+radius[i]+count]==str[i-radius[i]-count])
38                         count++;
39                     radius[i]+=(count-1);
40                     if(i+radius[i]>=rad){
41                         idx=i;
42                         rad=i+count;
43                     }
44                 }
45                 maxIdx=(radius[i]>radius[maxIdx]?i:maxIdx);
46             }
47             
48         }
49         string ret=getMaxSubString(str,maxIdx,radius[maxIdx]);
50         return ret;
51     }
52     void forceExtend(const string& str, vector<int>& radius,int &idx,int &rad,const int k){
53         int count=1;
54         while((k-count)>=0&&(k+count)<str.size()&&str[k-count]==str[k+count]){
55             count++;
56         }
57         radius[k]=count-1;
58         if(k+radius[k]>=rad){
59             idx=k;
60             rad=k+count;
61         }
62     }
63     string getMaxSubString(const string &str,const int k,const int r){
64         string ret(r,'0');
65         int j=0;
66         for(int i=k-r+1;i<=k+r;i+=2){
67             ret[j++]=str[i];
68         }
69         return ret;
70     }
71     
72 };