最长回文子串——C++

回文字符串：若一个字符串的逆置与它本身相同，这个字符串就是个回文字符串。

例：“”，“aa”，“b”，“aba”，“assbbssa”，“asdfdsa”

一个空字符串是回文的，单个字符的字符串也是回文的。

在给定字符串中查找回文子串的时候，可以以两字符和三字符的回文子串为基础，逐渐向两边扩展，直到不满足回文字符串的性质或者触碰到字符串边界为止，用这种方式来查找所有的回文子串，并给出最长的那一个。这种查找方法的最坏时间复杂的为O（n），最坏情况发生在字符串仅包含同一个字符的情况下。

#include <iostream>

using namespace std;

class Palindrome {
public:
    int boundary[2] = {0, 0}; //保存回文子串的边界下标
    
    //给定一个回文子串，以此子串为中心向两边扩展，试图查找最长的回文子串
    int* findBoundary(string s, int begin, int end){
        //记录字串边界
        boundary[0] = begin;
        boundary[1] = end;
        
        for(int i = 1;;i++){
            //当子串某一边的边界与母串重合，或者子串两端的字符不相等时，直接返回上次记录的字串边界
            if(begin - i < 0 || end + i > s.length() - 1 || s[begin-i] != s[end+i]){
                return boundary;
            }
            
            //子串两端的字符相等，更新边界值
            boundary[0] = begin - i;
            boundary[1] = end + i;
        }
    }
    
    string longestPalindrome(string s) {
        
        int n = s.length();
        
        //空字符串或者单字符串的最长回文子串就是它本身
        if(n == 1 || n == 0){
            return s;
        }
        
        //双字符的字符串，若两个字符相等，最长回文子串就是它本身，否则就是它的任意一个单字符
        if(n == 2){
            return (s[0] == s[1])?s:s.substr(0,1);
        }
        
        int len = 1;        //保存当前找到的最长回文子串的长度
        string result;      //保存结果
        int* p = nullptr;   //保存边界数组
        
        //先判断最后两个元素能否构成回文串
        if(s[n-1] == s[n-2]){
            len = 2;
            result = s.substr(n-2,2);
        }else{
            result = s.substr(0,1);
        }
        
        for(int i = 0; i < n-2; i++){
            //若两个相邻字符相等，以它们为最小回文子串向两边扩展
            if(s[i] == s[i+1]){
                p = findBoundary(s, i, i+1);
                //如果新的字串长度大于当前找到的最长回文子串的长度，更新len和result
                if(*(p+1) - *p + 1 > len){
                    len = *(p+1) - *p + 1;
                    result = s.substr(*p, len);
                }
            }
            
            //若三个字符串的两端相等，以它们为最小回文子串向两边扩展
            if(s[i] == s[i+2]){
                p = findBoundary(s, i, i+2);
                //如果新的字串长度大于当前找到的最长回文子串的长度，更新len和result
                if(*(p+1) - *p + 1 > len){
                    len = *(p+1) - *p + 1;
                    result = s.substr(*p, len);
                }
            }
        }
        
        return result;
    }
};

int main() {
    string s;
    cin >> s;
    string ret = Palindrome().longestPalindrome(s);
    return 0;
}