Submission #1102764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102764		vjudge1	Palindromes (APIO14_palindrome)	C++17	68 / 100	33 ms	65680 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct PAM {
    static constexpr int ALPHABET_SIZE = 26;
    struct Node {
        int len, fail;
        array<int, ALPHABET_SIZE> next;
        Node() : len{}, fail{}, next{} {}
    };
    vector<int> s;
    vector<Node> t;
    int lst;  // 用來追踪當前回文節點
    PAM() { init(); }
    void init() {
        t.assign(2, Node());
        s.clear(); 
        t[1].len = -1; // 奇數根節點
        t[0].len = 0, t[0].fail = 1; // 偶數根節點
        lst = 1;  // 初始 lst 為奇數根
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        int n = s.size();
        s.push_back(c);
        while (s[n - t[p].len - 1] != c)
            p = t[p].fail;
        if (!t[p].next[c]) {
            int r = newNode();
            t[r].len = t[p].len + 2;
            int cur = t[p].fail;
            while (s[n - t[cur].len - 1] != c)
                cur = t[cur].fail;
            t[r].fail = t[cur].next[c];
            t[p].next[c] = r;
        }
        return t[p].next[c];
    }
    void build_count(vector<int>& cnt) {
        // 計數累加到 fail 鏈
        for (int i = t.size() - 1; i > 1; --i) {
            cnt[t[i].fail] += cnt[i];
        }
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.length();
    vector<int> last(n + 1);
    vector<int> cnt(n + 1);  // 用於記錄每個回文節點的出現次數
    PAM pam;
    pam.init();
    for (int i = 0; i < n; i++) {
        pam.lst = pam.extend(pam.lst, s[i] - 'a');
        cnt[pam.lst]++;  // 統計每個回文節點的次數
    }

    pam.build_count(cnt);  // 累加 fail 鏈上的出現次數

    ll ans = 0;
    for (int i = 2; i < pam.t.size(); i++) {  
        ans = max(ans, 1LL * pam.t[i].len * cnt[i]);
    }

    cout << ans << "\n";

    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<PAM::Node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 2; i < pam.t.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27