Участник:S1td1kov/LongestPalindromeSubstring

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/longest-palindromic-substring/submissions/

//follow my github https://github.com/RusS1103/Leetcode
const int ZERO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
 
class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        if (len <= 1) return s;
 
        string ref(2 * len + 1, '#');
        for (int i = 0; i < len; i++) ref[2 * i + 1] = s[i];
 
        int max_id = 0;
        int max_rad = 0;
        for (int j = 0; j < ref.size(); j++) {
            int rad = 1;
            while(j - rad >= 0 && j + rad < ref.size() && ref[j - rad] == ref[j + rad]) rad++;
            if (rad > max_rad) {
                max_id = j;
                max_rad = rad;
            }
        }
        max_rad--;
 
        string res = ref.substr(max_id - max_rad, 2 * max_rad + 1);
        string result;
        for (int k = 0; k < res.size(); k++) {
            if (res[k] != '#') result.push_back(res[k]);
        }
        return result;
    }
};