Submission #1102775

#TimeUsernameProblemLanguageResultExecution timeMemory
1102775vjudge1Palindromes (APIO14_palindrome)C++17
76 / 100
29 ms64592 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

struct PAM {
    // 0 -> even root, 1 -> odd root
    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;
    PAM() { init(); }
    void init() {
        s.clear(); 
        t.assign(2, Node());
        t[0].len = 0, t[1].len = -1;
        t[0].fail = t[1].fail = 1;
    }
    int newNode() {
        t.emplace_back();
        return t.size() - 1;
    }
    int extend(int p, int c) {
        int i = s.size();
        s.push_back(c);
        while (s[i - t[p].len - 1] != c)
            p = t[p].fail;
        if (!t[p].next[c]) {
            int r = newNode(), v = t[p].fail;
            t[r].len = t[p].len + 2;
            while (s[i - t[v].len - 1] != c)
                v = t[v].fail;
            t[r].fail = t[v].next[c];
            t[p].next[c] = r;
        }
        return p = t[p].next[c];
    }
};

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

    string s;
    cin >> s;
    int n = s.length();
    vector<int> last(n + 1);
    last[0] = 1;
    PAM pam;
    for (int i = 0; i < n; i++) {
        last[i + 1] = pam.extend(last[i], s[i] - 'a');
    }

    int sz = pam.t.size();
    vector<int> cnt(sz);

    for (int i = 1; i <= n; i++) {
        cnt[last[i]]++; // 去重 = 1
    }
    ll ans = 0;
    for (int i = sz - 1; i >= 0; i--) {
        cnt[pam.t[i].fail] += cnt[i];
        ans = max(ans, 1LL * pam.t[i].len * cnt[i]);
    }

    cout << ans << "\n";




    // string s;
    // cin >> s;
    // int n = s.length();

    // PAM pam;
    // vector<int> last(n + 1);
    // last[0] = 1;
    // vector<int> a(n);
    // for (int i = 0; i < n; i++) {
    //     a[i] = s[i];
    // }

    // vector<int> ans(n + 1);
    // for (int i = 0; i < n; i++) {
    //     a[i] = (a[i] - 97 + ans[i]) % 26 + 97;
    //     last[i + 1] = pam.extend(last[i], a[i] - 'a');
    //     ans[i + 1] = cnt.back();
    // }

    // for (int i = 0; i < n; i++) {
    //     cout << ans[i + 1] << " \n"[i == n - 1];
    // }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...