LeetCode #5 最长回文子串

Manacher

class Solution {
public:
    string longestPalindrome(string s) {
        string t;
        int i,c,r,len,flag,j,i_,l,max,q;
        len=2*s.size()+1;
        flag=0;
        j=0;
        for(i=0;i<len;i++){
            t.push_back(flag==0?'#':s[j++]);
            flag=flag==0?1:0;
        }
        max=0;
        vector<int>p;
        c=-1;
        r=-1;
        i=0;
        while(i<len){
            if(i>r){
                j=1;
                while(i-j>=0&&i+j<=len-1){
                    if(t[i-j]==t[i+j]){
                        j++;
                    }
                    else{
                        break;
                    }
                }
            }
            else{
                l=2*c-r;
                i_=2*c-i;
                if(l==i_-p[i_]+1){
                    j=r-i;
                    while(i-j>=0&&i+j<=len-1){
                        if(t[i-j]==t[i+j]){
                            j++;
                        }
                        else{
                            break;
                        }
                    }
                }
                else{
                    j=l<i_-p[i_]+1?p[i_]:r-i+1;
                }
            }
            p.push_back(j);
            if(i+p[i]-1>r){
                r=i+p[i]-1;
                c=i;
            }
            if(p[i]>max){
                max=p[i];
                q=i;
            }
            i++;
        }
        string answer;
        answer.assign(s,(q-max+1)/2,max-1);
        return answer;
    }
};

注：

再提交时遇到了同一个测试用例在本地和提交结果不一样的情况，排查后发现是因为没有对max进行初始化导致了多个用例时出错，LeetCode建议不要使用类内静态变量和全局变量以及记得要初始化。