题解 | #密码截取#

密码截取

http://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1

题目的主要信息：

找出最长的对称密码可以转换为求最长回文。回文有两种形式，一种是形如ABA式对称的，另一种是形如ABBA式对称的。

方法一：中心扩展

遍历一遍字符串，计算每个字符为中点时能构成的最长回文串，输出最大的长度。判断字符串是否为回文串可以从中点出发向两边扩展，判断左右两侧是否相同，若相同则继续扩展；若不同，则停止扩展，计算当前的回文串长度。需要注意的是ABA式的回文串中点是一个字符，ABBA式回文串的中点是两个字符，所以我们遍历考虑每个字符当中点能构成的回文串时，这两种形式的长度都要计算。 alt

具体做法：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int getLen (string s, int l, int r) {
    while(l>=0&&r<=s.size()-1){//向左右扩展查找最大长度
        if(s[l]==s[r]){//s[l]==s[r]则继续扩展
            l--;
            r++;
        }else break;//s[l]不等于s[r]则查找结束
    }
    return r - l - 1;
}

// 中心扩展法（单双中心取最大）
int main () {
    string str;
    while(cin>>str){
        //处理边界情况
        if(str.size()==0){
            cout<<"0"<<endl;
            continue;
        }
        if(str.size()==1){
            cout<<"1"<<endl;
            continue;
        }
        //对于一般情况求解
        int maxLen=0;//保存最长的有效密码串的长度
        for(int i=0;i<str.size();i++){
            int len1=getLen(str,i,i);//ABA式对称
            int len2=getLen(str,i,i+1);//ABBA式对称
            len1=max(len1,len2);
            maxLen=max(maxLen,len1);//记录最大长度
        }
        cout<<maxLen<<endl;
    }
    return 0;
}

复杂度分析：

时间复杂度： $O (n^{2})$ ，最坏情况下整个字符串都为相同的字符，外循环遍历整个字符串需要 $O (n)$ ，getLen需要判断n-i次判断。
空间复杂度： $O (1)$ ，只用了常数空间。

方法二：Manacher算法

Manacher算法提供了一种巧妙的办法，将长度为奇数的回文串和长度为偶数的回文串一起考虑。在原字符串的每个相邻两个字符中间插入一个分隔符，同时在首尾也要添加一个分隔符，分隔符的要求是不在原串中出现，一般情况下可以用#号，同时为了防止越界，在字符串头加上一个其他字符防止越界。 alt

先从左往右依次计算len[i]，设mx为之前计算中最长回文子串的右端点的最大值，并且设取得这个最大值的位置为id，j为i关于id的对称点。当计算len[i]时，len[j] (0<=j<i)已经计算完毕。 alt

分两种情况：

i<mx。len[i]先初始化为len[j]和mx-i中的最小值，而后再向左右两边扩散求解。
i>=mx。需要从位置i开始逐一向左右两边扩散比较。

计算完len[i]之后和当前的mx进行比较，更新最大回文串的信息。

具体做法：

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int manacher(string s){
    string s1="$#";//开头加一个字符，防止越界
    for(int i=0;i<s.size();i++)
    {
        s1+=s[i];
        s1+='#';
    }
    int pos=0;//当前最长回文串的中点
    int mx=0;//当前最长回文子串的中点到右端点的长度
    int maxlen=0;
    vector<int> len(s1.size());
    for(int i=0;i<s1.size();i++)
    {
        if(i<mx){
            len[i]=min(mx-i,len[2*pos-i]);//判断和对称位置的回文串长度比较
        }else{
            len[i]=1;
        }
        while(s1[i+len[i]]==s1[i-len[i]]){//向两边扩展
            len[i]++;
        }
        if(len[i]>mx){//更新最长回文串信息
            pos=i;//位置
            mx=len[i]+1;//长度
        }
        maxlen=max(maxlen,len[i]-1);
    }
    return maxlen;
}
    
int main(){
    string str;
    while(cin>>str){
        cout<<manacher(str)<<endl;//manacher算法
    }
    return 0;
}

复杂度分析：