Submission #375872

#TimeUsernameProblemLanguageResultExecution timeMemory
375872KoDPalindromes (APIO14_palindrome)C++17
47 / 100
202 ms27312 KiB
#include <bits/extc++.h>

int rand_int(const int low, const int high) {
    static std::random_device dev;
    static std::default_random_engine gen(dev() ^ std::clock());
    return std::uniform_int_distribution<int>(low, high)(gen);
}

constexpr int MOD = 1000000007;
const int BASE = rand_int(0, MOD - 1);

constexpr int sum(int x, const int y) {
    x += y;
    return (x >= MOD ? x - MOD : x);
}

constexpr int prod(const int x, const int y) {
    return ((long long) x * y) % MOD;
}

template <class T>
using Vec = std::vector<T>;

struct RollingHash {
    Vec<int> pow, dp;
    RollingHash(const std::string &str) {
        const int size = (int) str.size();
        pow.resize(size + 1);
        dp.resize(size + 1);
        pow[0] = 1;
        dp[1] = 0;
        for (int i = 0; i < size; ++i) {
            pow[i + 1] = prod(pow[i], BASE);
            dp[i + 1] = sum(prod(dp[i], BASE), (int) str[i]);
        }
    }
    int hash(const int l, const int r) const {
        return sum(dp[r], MOD - prod(dp[l], pow[r - l]));
    }
};

template <class T, class U>
using HashTable = __gnu_pbds::gp_hash_table<T, U>;

struct Range {
    int l, r;
    Range(const int l, const int r): l(l), r(r) { }
    bool operator < (const Range &other) const {
        return r - l < other.r - other.l;
    }
};

int main() {
    std::string S;
    std::cin >> S;
    const int N = (int) S.size();
    RollingHash rh(S);
    RollingHash rh_rev(std::string(S.rbegin(), S.rend()));
    const auto is_palindrome = [&](const int l, const int r) {
        if (l < 0 || r > N) {
            return false;
        }
        return rh.hash(l, r) == rh_rev.hash(N - r, N - l);
    };
    std::priority_queue<Range> heap;
    HashTable<int, int> count;
    const auto add = [&](const int l, const int r, const int x) {
        const auto hash = rh.hash(l, r);
        if (count[hash] == 0) {
            heap.emplace(l, r);
        }
        count[hash] += x;
    };
    for (int i = 0; i < N; ++i) {
        int ok = 0, ng = N + 1;
        while (ng - ok > 1) {
            const auto md = (ok + ng) / 2;
            if (is_palindrome(i - md, i + md + 1)) {
                ok = md;
            }   
            else {
                ng = md;
            }
        }
        add(i - ok, i + ok + 1, 1);
    }   
    for (int i = 1; i < N; ++i) {
        if (S[i - 1] != S[i]) {
            continue;
        }
        int ok = 1, ng = N + 1;
        while (ng - ok > 1) {
            const auto md = (ok + ng) / 2;
            if (is_palindrome(i - md, i + md)) {
                ok = md;
            }   
            else {
                ng = md;
            }
        }
        add(i - ok, i + ok, 1);
    }
    long long ans = 0;
    while (!heap.empty()) {
        const auto [l, r] = heap.top();
        heap.pop();
        const auto c = count[rh.hash(l, r)];
        ans = std::max(ans, (long long) c * (r - l));
        if (r - l > 2) {
            add(l + 1, r - 1, c);
        }
    }
    std::cout << ans << '\n';
    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...