题解 | #最长回文子串#

最长回文子串，也即最长对称子串，显然有两种类型，aba型和abba型。

思路：遍历两次字符串s，先计算aba型子串的最长长度，再计算abba型。

#include<iostream>
#include<string>

using namespace std;

int main() {
    string s;
    cin >> s;
    int i;
    int maxsubstr = 1;//最长回文子串最短为1
    for (i = 0; i < s.size(); ++i) { //先计算aba型
        int len_aba = 1;
        int m = i - 1, n = i + 1;//保证m和n的合法性
        while (m >= 0 && n < s.size() && s[m] == s[n]) {
            len_aba += 2;
            m--;
            n++;
        }
        if (maxsubstr < len_aba) {
            maxsubstr = len_aba;
        }
    }
    for (i = 0; i < s.size(); ++i) { //再计算abba型
        int len_abba = 0;
        int m = i, n = i + 1;
        while (m >= 0 && n < s.size() && s[m] == s[n]) {
            len_abba += 2;
            m--;
            n++;
        }
        if (maxsubstr < len_abba) {
            maxsubstr = len_abba;
        }
    }
    cout << maxsubstr << endl;
    return 0;
}