Submission #197038

#TimeUsernameProblemLanguageResultExecution timeMemory
197038mario05092929Palindromes (APIO14_palindrome)C++11
100 / 100
63 ms37524 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<int N_,int A> struct pal_tree
{
    const static int N = N_ + 2;
    int n, s[N], suff[N];
    int k, len[N], occ[N], to[N][A], link[N];

    pal_tree() : n(0), k(0) {
        palindrome(0, 1);
        palindrome(-1, 1);
        letter(-1, 0);
    }

    int palindrome(int l, int suf) {
        len[k] = l;
        occ[k] = 0;
        fill_n(to[k], A, 0);
        link[k] = suf;
        return k++;
    }

    int letter(int val, int suf) {
        s[n] = val;
        suff[n] = suf;
        occ[suf]++;
        return n++;
    }

    int trim(int u) {
        while (s[n - 1 - len[u]] != s[n])
        {
            u = link[u];
        }
        return u;
    }

    void put(int c) {
        s[n] = c;
        int u = trim(suff[n - 1]);
        if (!to[u][c]) {
            int v = trim(link[u]);
            to[u][c] = palindrome(len[u] + 2, to[v][c]);
        }
        letter(c, to[u][c]);
    }

    int distinct() {
        return k - 2;
    }

    void occurrences() {
        for (int u = k - 1; u > 1; u--) {
            occ[link[u]] += occ[u];
        }
    }
    void clear() {n = 1;}
};

pal_tree<300000,26> t;

int main() {
    string s;
    cin >> s;
    for(char c : s) t.put(c - 'a');
    ll ans = 1;
    t.occurrences();
    for (int i = 2; i < t.k;i++) {
        ans = max(ans, (long long) t.occ[i] * t.len[i]);
    }
    cout << ans;
}
#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...