---
tags: APIO
---
# APIO2014-1 Palindromes

シラバス外を出すのをやめなさ〜い！

## 問題

https://oj.uz/problem/view/APIO14_palindrome

文字列 $S$ がある。 文字列 $S$ について、回文 $T$ の出現度を $|T| \times S.{\rm count}(T)$ として定める。 出現度の最大値を求めよ。

## 考察

とりあえず回文なので Manacher's Algorithm で回文を列挙する

ここからがなにもわからない

ところでここに自然なびっくりfactがある
http://sigma425.hatenablog.com/entry/2015/07/09/223850

これを知ってないときびしい

#### [定理] 長さ $N$ の文字列の部分文字列として現れる回文は $N$ 種類以下である

帰納法で示す : (長さ $N$ の文字列) に 'A' を加えると高々 1 種類しか増えない

新たに 2 種類以上の回文ができると仮定する

`A______A__` + `A` のような状況を考える

`A______A__A` 新しくできた 2 つが回文だとすると

`A__A___A__A` じつはここにも A があって

最長のもの以外は実はすでにあったものだとわかる
<br>

Manacher で出た最長回文を priority_queue に入れて長い回文から短いほうに累積和をとると、
各回文の出現回数がわかって、上の定理より、これは $O(N\log N)$ になることがわかる

## ところで

[IOI Syllabus 2019](https://ioinformatics.org/files/ioi-syllabus-2019.pdf) によると、 String algorithms and data structures は "Excluded, but open to discussion" であるため、 Manacher's Algorithm は覚えなくてよさそう

## 実装

oj.uz の gcc が 7.3.0 なので、クラステンプレート引数の推論ができず悲しい…

https://oj.uz/submission/229784

#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
 
constexpr ull mod = 0x1fffffffffffffff, base = 257;
struct RollingHash{
    const int n;
    vector<ull> data, power;
    static constexpr ull mul(ull a, ull b){
        u128 c = (u128)a * b;
        ull ans = ull(c >> 61) + ull(c & mod);
        if(ans >= mod) ans -= mod;
        return ans;
    }
    RollingHash(const string& s): n(s.size()), data(n + 1), power(n + 1){
        power[0] = 1;
        data[0] = 1;
        for(int i = 0; i < n; i++){
            power[i + 1] = mul(power[i], base);
            data[i + 1] = mul(data[i], base) + s[i];
            if(data[i + 1] >= mod) data[i + 1] -= mod;
        }
    }
    ull get(int l, int r){
        const ull L = mul(data[l], power[r - l]);
        const ull R = data[r];
        return R - L + (R < L ? mod : 0);
    }
};
vector<int> manacher(const string& S){
    string s = {S[0]};
    for(int i = 1; i < S.size(); i++){
        s += '$';
        s += S[i];
    }
    const int n = s.size();
    vector a(n, 0);
    for(int i = 0, j = 0; i < n; ){
        while(i - j >= 0 && i + j < n && s[i - j] == s[i + j]) j++;
        a[i] = j;
        int k = 1;
        for(; i - k >= 0 && i + k < n && k + a[i - k] < j; k++) a[i + k] = a[i - k];
        i += k;
        j -= k;
    }
    return a;
}
int main(){
    string s;
    cin >> s;
    RollingHash rh(s);
    auto a = manacher(s);
    auto comp = [](pii a, pii b){ return a.second - a.first < b.second - b.first; };
    priority_queue<pii, vector<pii>, decltype(comp)> q(comp);
    unordered_map<ull, ull> cnt;
    for(int i = 0; i < a.size(); i++){
        int l = (i - a[i] + 2) / 2, r = (i + a[i] + 1) / 2;
        if(l >= r) continue;
        auto [iter, changed] = cnt.try_emplace(rh.get(l, r), 0);
        if(changed) q.emplace(l, r);
        iter->second++;
    }
    ull ans = 0;
    while(q.size()){
        auto [l, r] = q.top();
        q.pop();
        ull a = cnt[rh.get(l, r)];
        chmax(ans, a * (r - l));
        l++; r--;
        if(l < r){
            auto [iter, changed] = cnt.try_emplace(rh.get(l, r), 0);
            if(changed) q.emplace(l, r);
            iter->second += a;
        }
    }
    cout << ans << endl;
}