Submission #344470

#	Time	Username	Problem	Language	Result	Execution time	Memory
344470		12tqian	Palindromes (APIO14_palindrome)	C++17	15 / 100	419 ms	53776 KiB

palindrome

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

#define f1r(i, a, b) for (int i = a; i < b; i++) 
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;


template <class T> struct SparseTable {
    std::vector<T> v;
    std::vector<std::vector<int>> jump;
    int level(int x) {
        return 31 - __builtin_clz(x);
    }
    int comb(int a, int b) {
        return v[a] == v[b] ? std::min(a, b) : (v[a] < v[b] ? a : b);
    }
    void init(const std::vector<T>& _v) {
        v = _v;
        jump = {std::vector<int>((int) v.size())};
        iota(jump[0].begin(), jump[0].end(), 0);
        for (int j = 1; (1 << j) <= (int) v.size(); j++) {
            jump.push_back(std::vector<int>((int) v.size() - (1 << j) + 1));
            for (int i = 0; i < (int) jump[j].size(); i++) 
                jump[j][i] = comb(jump[j - 1][i], jump[j - 1][i + (1 << (j - 1))]);
        }
    }
    int index(int l, int r) {
        assert(l <= r);
        int d = level(r - l + 1);
        return comb(jump[d][l], jump[d][r - (1 << d) + 1]);
    }
    T query(int l, int r) {
        return v[index(l, r)];
    }
};

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i,0,a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)
#define R0F(i, a) ROF(i, 0, a)
#define trav(a, x) for (auto& a : x)
typedef string str;
template<class T> struct RMQ { // floor(log_2(x))
    int level(int x) { return 31-__builtin_clz(x); } 
    vector<T> v; vector<vi> jmp;
    int comb(int a, int b) { // index of min
        return v[a]==v[b]?min(a,b):(v[a]<v[b]?a:b); } 
    void init(const vector<T>& _v) {
        v = _v; jmp = {vi(sz(v))}; iota(all(jmp[0]),0);
        for (int j = 1; 1<<j <= sz(v); ++j) {
            jmp.pb(vi(sz(v)-(1<<j)+1));
            F0R(i,sz(jmp[j])) jmp[j][i] = comb(jmp[j-1][i],
                                    jmp[j-1][i+(1<<(j-1))]);
        }
    }
    int index(int l, int r) { // get index of min element
        assert(l <= r); int d = level(r-l+1);
        return comb(jmp[d][l],jmp[d][r-(1<<d)+1]); }
    T query(int l, int r) { return v[index(l,r)]; }
};
struct SuffixArray {
    str S; int N; vi sa, isa, lcp;
    void init(str _S) { N = sz(S = _S)+1; genSa(); genLcp(); }
    void genSa() {
        sa = isa = vi(N); sa[0] = N-1; iota(1+all(sa),0);
        sort(1+all(sa),[&](int a, int b) { return S[a] < S[b]; });
        FOR(i,1,N) { int a = sa[i-1], b = sa[i];
            isa[b] = i > 1 && S[a] == S[b] ? isa[a] : i; }
        for (int len = 1; len < N; len *= 2) { // currently sorted by first len chars
            vi s(sa), is(isa), pos(N); iota(all(pos),0); 
            trav(t,s) { int T = t-len; if (T >= 0) sa[pos[isa[T]]++] = T; }
            FOR(i,1,N) { int a = sa[i-1], b = sa[i];
                isa[b] = is[a] == is[b] && is[a+len] == is[b+len] ? isa[a] : i; }
        }
    }
    void genLcp() { // Kasai's Algo
        lcp = vi(N-1); int h = 0;
        F0R(b,N-1) { int a = sa[isa[b]-1];
            while (a+h < sz(S) && S[a+h] == S[b+h]) h ++;
            lcp[isa[b]-1] = h; if (h) h--; }
        R.init(lcp); /// if we cut off first chars of two strings
        /// with lcp h then remaining portions still have lcp h-1 
    }
    RMQ<int> R; 
    int getLCP(int a, int b) { // lcp of suffixes starting at a,b
        if (a == b) return sz(S)-a;
        int l = isa[a], r = isa[b]; if (l > r) swap(l,r);
        return R.query(l,r-1);
    }
};
// struct SuffixArray {
//     int n;
//     std::vector<int> sa, isa, lcp;
//     std::string s;
//     SparseTable<int> S;
//     void init(std::string s_) {
//         n = (int) (s = s_).size() + 1;
//         gen_suffix_array();
//         gen_lcp_array();
//     }
//     void gen_suffix_array() {
//         sa = isa = std::vector<int>(n);
//         sa[0] = n - 1;
//         iota(1 + sa.begin(), sa.end(), 0);
//         sort(1 + sa.begin(), sa.end(), [&](int a, int b) {
//             return s[a] < s[b]; });
//         for (int i = 1; i < n; i++) {
//             int a = sa[i - 1], b = sa[i];
//             isa[b] = i > 1 && s[a] == s[b] ? isa[a] : i;
//         }
//         for (int len = 1; len < n; len *= 2) { 
//             std::vector<int> ss(sa), is(isa), pos(n);
//             iota(pos.begin(), pos.end(), 0);
//             for (auto& t : ss) {
//                 int tt = t - len;
//                 if (tt >= 0) 
//                     sa[pos[isa[tt]]++] = tt;
//             }
//             for (int i = 1; i < n; i++) {
//                 int a = sa[i - 1], b = sa[i];
//                 isa[b] = is[a] == is[b] && is[a + len] == is[b + len] ? isa[a] : i;
//             }
//         }
//         sa.erase(sa.begin());
//     }
//     void gen_lcp_array() {
//         lcp = std::vector<int>(n - 1);
//         int h = 0;
//         for (int b = 0; b < n - 1; b++) {
//             int a = sa[isa[b]];
//             while (a + h < (int) s.size() && s[a + h] == s[b + h])
//                 h++;
//             lcp[isa[b] - 1] = h;
//             if (h)
//                 h--;
//         }
//         S.init(lcp);
//     }
//     int get_lcp(int a, int b) {
//         if (a == b) 
//             return (int) s.size() - a;
//         int l = isa[a], r = isa[b];
//         if (l > r) 
//             std::swap(l, r);
//         return S.query(l, r - 1);
//     }
// };

std::vector<int> manacher(std::string s) {
    std::string t = "@";
    for (auto& c : s) 
        t += c, t += '#';
    t.back() = '&';
    std::vector<int> res((int) t.size() - 1);
    int lo = 0, hi = 0;
    for (int i = 1; i < (int) t.size() - 1; i++) {
        if (i != 1)
            res[i] = std::min(hi - i, res[hi - i + lo]);
        while (t[i - res[i] - 1] == t[i + res[i] + 1])
            res[i]++;
        if (i + res[i] > hi)
            lo = i - res[i], hi = i + res[i];
    }
    res.erase(res.begin());
    for (int i = 0; i < (int) res.size(); i++)
        if ((i & 1) == (res[i] & 1))
            res[i]++;
    return res;
}
ll solve(vi v) {
    int n = sz(v);
    SparseTable<int> S; S.init(v);
    ll ret = 0;
    f0r(i, n) {
        int l, r;
        {
            int lo = 0;
            int hi = i;
            while (hi - lo > 1) {
                int mid = (lo + hi) / 2;
                if (S.query(mid, i) == v[i]) hi = mid;
                else lo = mid + 1;
            }
            if (S.query(lo, i) == v[i]) l = lo;
            else l = hi;
        }
        {
            int lo = i;
            int hi = n-1;
            while (hi - lo > 1) {
                int mid = (lo + hi) / 2;
                if (S.query(i, mid) == v[i]) lo = mid;
                else hi = mid - 1;
            }
            if (S.query(i, hi) == v[i]) r = hi;
            else r = lo;
        }
        ret = max(ret, 1LL * (r - l + 2) * v[i]);
    }
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    string s; cin >> s;
    int n = sz(s);
    SuffixArray S; S.init(s);
    vi m = manacher(s);
    ll ans = 0;
    // take care of palindromes that occur exactly once
    // We'll consider PAL the 'extension'
    for (ll x : m) ans = max(ans, x);
    {
        // handle even palindromes
        // even length palindrome
        // say loc i, len L
        // consider a contiguous array in suffix array
        // [l, r]
        // Say they have lcp of x
        // min(x, min(PAL [l, r])) * 2 * (r - l + 1)
        // each thing has in common at most x
        // and each loc has palinndrome size at most PAL
        // replace with inner splices, set to min(lcp, PAL[i, i+1]) * 2
        // maximize min(l, r) * (r - l + 1) is the new problem?
        // check the min gap
        // and bash
        // okay that works
        vi pal(n);
        f0r(i, n) {
            if (i) pal[i] = m[2*i-1] / 2;
        }
        vi use(n-1);
        f0r(i, n-1) {
            int i1 = S.sa[i];
            int i2 = S.sa[i+1];
            int val = min(pal[i1], pal[i2]);
            val = min(S.getLCP(i1, i2), val);
            val *= 2;
            use[i] = val;
        }
        ans = max(ans, solve(use));
    }
    {
        // handle odd palindromes
        // consider a contiguous array in suffix array
        // [l, r]
        // say they have lcp of x
        // We're considering all of these as the center piece
        // (min(x - 1, min(PAL [l, r])) * 2 + 1) * (r - l + 1)
        // replace with inner splices, set to min(lcp - 1, PAL[i, i+1]) * 2 + 1
        // maximize min(l, r) * (r - l + 1) 
        // same sub problem
        vi pal(n);
        f0r(i, n) {
            pal[i] = m[2*i] / 2;
        }
        vi use(n-1);
        f0r(i, n-1) {
            int i1 = S.sa[i];
            int i2 = S.sa[i+1];
            int val = min(pal[i1], pal[i2]);
            val = min(val, S.getLCP(i1, i2) - 1);
            val = 2 * val + 1;
            use[i] = val;
        }
        ans = max(ans, solve(use));
        // f0r(i, n) cout << S.sa[i] << " " ;
        // cout << endl;
        // f0r(i, n-1) cout << S.getLCP(i, i+1) << " " ;
        // cout << endl;
        // f0r(i, n) cout << pal[i] << " ";
        // cout << endl;
        // f0r(i, n-1) cout << use[i] << " ";
        // cout << endl;
        // f0r(i, n-1) {
        //     cout << S.getLCP(S.sa[i], S.sa[i+1]) << " ";
        // }
        // cout << endl;
    }
    cout << ans << '\n';
    return 0;
}

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