题解：AT1202Contest_e Half Palindromes

#include #include #include #include using namespace std;

// Manacher算法计算最长回文子串半径（奇数长度） vector manacher_odd(const string &s) { int n = s.size(); vector p(n); int l = 0, r = -1; for (int i = 0; i < n; ++i) { int k = (i > r) ? 1 : min(p[l + r - i], r - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) { k++; } p[i] = k--; if (i + k > r) { l = i - k; r = i + k; } } return p; }

int main() { string S; cin >> S; int n = S.size(); if (n == 0) { cout << 0 << endl; return 0; }

CPP

// 计算每个位置的最长奇数长度回文半径
vector<int> p = manacher_odd(S);

long long t = 0;

// 枚举所有子串S[i..j]
for (int i = 0; i < n; ++i) {
    // 对于每个i，找到最大的回文半径中心
    int max_r = 0;
    for (int c = i; c < n; ++c) {
        // 计算以c为中心，覆盖i的最大半径
        int possible_r = min(p[c], c - i + 1);
        max_r = max(max_r, possible_r);
        
        int len = c - i + 1;
        // 计算当前子串的最小长度
        int min_len = len - (max_r - 1);
        t+= min_len;
    }
}

cout << t << endl;
return 0;

}

题解：AT1202Contest_e Half Palindromes

文章操作

相关推荐

评论

题解：AT1202Contest_e Half Palindromes