题解 | #密码截取#时间空间都是O(n)

#include <iostream>
using namespace std;


int main() {
    string s;
    while(getline(cin,s)){
        int max=1;
        
        /*记录第i个字符对应的数据，该数据只和最长长度有关
        负数表示前-ss[i]个(包括自己)都是相同的字符(并且对称)
        正数表示下标i+1-ss[i]到i位置的字符串对称且字符不全相同
        按以上规则更新数组数据，遍历一遍，时间O(n)，空间O(n)*/
        int data[s.size()];
        
        data[0]=-1;
        for(int i =1;i<s.size();i++){
            if(data[i-1]<0){//前一个记录小于零
            if(s[i]==s[i-1]){//字符与前一个相等
            data[i]=data[i-1]-1;
            if(max<-data[i])   max=-data[i];
            }//字符与前一个不相等
            else if(i+data[i-1]-1>=0 &&s[i]==s[i+data[i-1]-1]){
                //字符与全相同字符串的前一个字符相同
                data[i]=2-data[i-1];
                if(max<data[i])  max=data[i];
            }
            else data[i]=-1;//与前面构不成任何对称字符串
            
            }
            else{
        //前一个记录大于零,注意！！！记录的绝对值是最大对称串长度
        //可能会有单字符字符串
                if(i-1-data[i-1]>=0 && s[i]==s[i-1-data[i-1]]){
                    data[i]=data[i-1]+2;
                    if(max<data[i])  max=data[i];
                }
                else {
                    data[i] =-1;
                    int j=i-1;
                    while(j>=0 && s[i]==s[j]){
                        j--;
                        data[i]--;
                    }
                    if(max<-data[i])   max=-data[i];
                }
            }
            
        }
        cout << max << endl;


    }
    return 0;
}