Submission #493448

#	Time	Username	Problem	Language	Result	Execution time	Memory
493448		aanji	회문 (APIO14_palindrome)	C++17	100 / 100	54 ms	63008 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

struct pal_tree {
    #define sigma 26
    struct node {
        int len, dep, cnt, slink;
        int to[sigma];
        node(int _len = 0, int _dep = 0, int _cnt = 0, int _slink = 0) {
            len = _len; dep = _dep; cnt = _cnt; slink = _slink;
            for (int i = 0; i < sigma; i++) {
                to[i] = 0;
            }
        }
    };
    int suff; string s;
    vector<node> tree;
    void init() {
        tree.clear(); s = ""; suff = 2;
        tree.push_back(node(0, 0, 0, 0));
        tree.push_back(node(-1, 0, 0, 1));
        tree.push_back(node(0, 0, 0, 1));
    }
    void add_letter(char c) {
        s += c; int len = s.size();
        while (c != s[len - 2 - tree[suff].len]) {
            suff = tree[suff].slink;
        }
        int nxt = tree[suff].to[c - 'a'];
        if (!nxt) {
            nxt = tree.size();
            tree[suff].to[c - 'a'] = nxt;
            tree.push_back(node(tree[suff].len + 2, 0, 0, 0));
            if (suff == 1) {
                tree[nxt].slink = 2;
            }
            else {
                int z = tree[suff].slink;
                while (c != s[len - 2 - tree[z].len]) {
                    z = tree[z].slink;
                }
                tree[nxt].slink = tree[z].to[c - 'a'];
            }
            tree[nxt].dep = tree[tree[nxt].slink].dep + 1;
        }
        tree[nxt].cnt++; suff = nxt;
    }
    void calc_cnt() {
        for (int i = tree.size() - 1; i > 2; i--) {
            tree[tree[i].slink].cnt += tree[i].cnt;
        }
    }
    node &operator[](int i) {
        return tree[i];
    }
} pt;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    string s; cin >> s;
    pt.init();
    for (char i : s) {
        pt.add_letter(i);
    }
    pt.calc_cnt();
    long long res = 0;
    for (int i = pt.tree.size() - 1; i > 2; i--) {
        res = max(res, (long long)(pt.tree[i].len) * pt.tree[i].cnt);
    }
    cout << res << endl;
    return 0;
}

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