結果

問題 No.263 Common Palindromes Extra
コンテスト
ユーザー coindarw
提出日時 2024-07-17 22:42:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 8,225 bytes
コンパイル時間 2,191 ms
コンパイル使用メモリ 143,696 KB
実行使用メモリ 184,544 KB
最終ジャッジ日時 2024-07-17 22:43:32
合計ジャッジ時間 7,837 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <set>
#include <vector>
typedef long long ll;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define inf int(2e9)
using namespace std;

vector<int> sa_is(vector<int> v, int upper) {
    // 1 <= v[i] <= upper
    if (v.size() == 0) return vector<int>();
    else if (v.size() == 1) return vector<int>(1, 0);
    else if (v.size() == 2) {
        vector<int> res(2, 0);
        if (v[0] < v[1]) res[1] = 1;
        else res[0] = 1;
        return res;
    }
    v.push_back(0);  // sentinel
    const int n = v.size();

    vector<int> bl(upper + 1), br(upper + 1);  // bucket range
    for (int i = 0; i < n; ++i) br[v[i]]++;
    for (int i = 1; i <= upper; ++i) br[i] += br[i - 1];
    for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1];

    vector<int> is_l(n);
    vector<int> lms, sa(n, -1), lms_ord(n);  // lms_ord[i] := 0 -> not lms, 1~ -> 1-indexed
    for (int i = n - 2; i >= 0; --i) is_l[i] = (v[i] == v[i + 1]) ? is_l[i + 1] : (v[i] > v[i + 1]);
    for (int i = 1; i < n; ++i) {
        if (!is_l[i] && is_l[i - 1]) {
            sa[--br[v[i]]] = i;
            lms_ord[i] = ~int(lms.size());
            lms.push_back(i);
        }
    }

    for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
    br[upper] = n;

    for (int i = 0; i < n; ++i)
        if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bl[v[sa[i] - 1]]++] = sa[i] - 1;
    for (int i = 1; i <= upper; ++i) bl[i] = br[i - 1];
    for (int i = 1; i < n; i++)
        if (sa[i] > -1 && !is_l[sa[i]]) sa[i] = -1;
    for (int i = n - 1; i >= 1; i--)
        if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--br[v[sa[i] - 1]]] = sa[i] - 1;
    for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
    br[upper] = n;

    vector<int> lms_substr_sorted(lms.size());
    int cnt = 0;
    for (int i = 0; i < n; ++i)
        if (sa[i] > -1 && lms_ord[sa[i]]) lms_substr_sorted[cnt++] = sa[i];

    // same lms_substr -> same rank
    vector<int> ord(lms.size());
    ord[0] = 1;
    for (int i = 0; i < int(lms.size()) - 1; ++i) {
        int l1 = lms_substr_sorted[i], l2 = lms_substr_sorted[i + 1];
        if (l1 > l2) swap(l1, l2);
        if (l2 == n - 1) ord[i + 1] = ord[i] + 1;
        else {
            int p1 = l1, p2 = l2;
            bool f = true;
            while (p1 <= lms[~lms_ord[l1] + 1] && p2 < n)
                if (v[p1] == v[p2]) ++p1, ++p2;
                else {
                    f = false;
                    break;
                }
            ord[i + 1] = f ? ord[i] : ord[i] + 1;
        }
    }
    vector<int> va(lms.size());  // make array of appearance order

    for (int i = 0; i < int(lms.size()); ++i) va[~lms_ord[lms_substr_sorted[i]]] = ord[i];

    vector<int> lms_sorted = sa_is(va, ord.back());

    // place lms at correct position
    fill(sa.begin(), sa.end(), -1);
    for (int i = lms.size() - 1; i >= 0; i--) sa[--br[v[lms[lms_sorted[i]]]]] = lms[lms_sorted[i]];
    for (int i = 0; i < upper; ++i) br[i] = bl[i + 1];
    br[upper] = n;
    for (int i = 0; i < n; ++i)
        if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bl[v[sa[i] - 1]]++] = sa[i] - 1;
    for (int i = 1; i < n; i++)
        if (sa[i] > -1 && !is_l[sa[i]]) sa[i] = -1;
    for (int i = n - 1; i >= 1; i--)
        if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--br[v[sa[i] - 1]]] = sa[i] - 1;
    sa.erase(sa.begin());
    return sa;
}
vector<int> sa_is(string s) {
    vector<int> v(s.size());
    for (int i = 0; i < int(s.size()); i++) v[i] = s[i];
    return sa_is(v, 255);
}
vector<int> lcp(const string& s, const vector<int>& sa) {
    assert(sa.size() == s.size());
    vector<int> rank(s.size()), _lcp(s.size() - 1);
    const int n = s.size();
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    int h = 0;
    for (int i = 0; i < n; i++) {
        if (rank[i] == 0) continue;
        int j = sa[rank[i] - 1];
        if (h > 0) h--;
        for (; j + h < n && i + h < n; h++)
            if (s[j + h] != s[i + h]) break;
        _lcp[rank[i] - 1] = h;
    }
    return _lcp;
}

vector<int> manacher(const string& s) {
    const int n = s.size();
    int i = 0, j = 0;
    vector<int> res(n);
    while (i < n) {
        while (i - j >= 0 && i + j < n && s[i - j] == s[i + j]) ++j;
        res[i] = j;
        int k = 1;
        while (i - k >= 0 && k + res[i - k] < j) res[i + k] = res[i - k], ++k;
        i += k, j -= k;
    }
    return res;
}

template <typename T, T INF>
class SparseTableMin {
    vector<vector<T>> st;
    vector<int> lookup;
    int n, N, logN;

    int __bit_ceil(int num) { return 1 << (32 - __builtin_clz(num)); }

   public:
    SparseTableMin() {}
    SparseTableMin(const vector<T>& v) {
        n = v.size();
        if (n == 0) return;
        N = __bit_ceil(v.size());
        logN = 32 - __builtin_clz(N);
        st.assign(logN, vector<T>(N, INF));
        for (int i = 0; i < n; i++) st[0][i] = v[i];
        int len = 1;
        for (int i = 1; i < (int)st.size(); i++) {
            for (int j = 0; j + len < N; j++) {
                st[i][j] = min(st[i - 1][j], st[i - 1][j + len]);
            }
            len <<= 1;
        }
        lookup.resize(N + 1);
        for (int i = 2; i < (int)lookup.size(); i++) lookup[i] = lookup[i >> 1] + 1;
    }

    T prod(int l, int r) {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return INF;
        int b = lookup[r - l];
        return min(st[b][l], st[b][r - (1 << b)]);
    }
};

vector<pair<int, int>> enumerate_palindromes(const string& s, const vector<int>& sa, const vector<int>& la) {
    const int n = s.size();
    vector<pair<int, int>> res;
    string t(n * 2 - 1, '$');
    for (int i = 0; i < n; ++i) t[i * 2] = s[i];

    SparseTableMin<int, inf> st(la);
    vector<int> rev_sa(n);
    for (int i = 0; i < n; ++i) rev_sa[sa[i]] = i;

    vector<int> man = manacher(t);
    vector<set<int>> lefts(n + 1);

    for (int i = 0; i < n * 2 - 1; ++i) {
        for (int rad = man[i]; rad > 0; --rad) {
            int l = i - (rad - 1);
            int r = i + (rad - 1);
            if (l % 2 != 0) continue;
            l = l / 2;
            r = r / 2 + 1;
            int len = r - l;
            auto ub = lefts[len].upper_bound(rev_sa[l]);
            if (ub != lefts[len].end()) {
                if (st.prod(min(rev_sa[l], *ub), max(rev_sa[l], *ub)) >= len) {
                    break;
                }
            }
            if (ub != lefts[len].begin()) {
                ub--;
                if (st.prod(min(rev_sa[l], *ub), max(rev_sa[l], *ub)) >= len) {
                    break;
                }
            }
            lefts[len].insert(rev_sa[l]);
            res.emplace_back(l, r);
        }
    }

    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin >> s >> t;

    auto count_palindrome_pairs = [](string str) -> ll {
        auto sa = sa_is(str);
        auto la = lcp(str, sa);
        auto pal = enumerate_palindromes(str, sa, la);
        vector<int> rev(str.size());
        rep(i, str.size()) rev[sa[i]] = i;
        SparseTableMin<int, inf> st(la);

        ll res = 0;
        for (auto [l, r] : pal) {
            auto bsearch = [&](auto cmp, int ok, int ng) {
                while (abs(ng - ok) > 1) {
                    int mid = (ng + ok) / 2;
                    if (cmp(mid)) ok = mid;
                    else ng = mid;
                }
                return ok;
            };
            // [l, r)とのLCPがr-l以上のものの個数を数える
            ll ls = bsearch([&](int x) { return st.prod(min(rev[l], rev[l] - x), max(rev[l], rev[l] - x)) >= r - l; }, 0, 1 + rev[l]);
            ll rs = bsearch([&](int x) { return st.prod(min(rev[l], rev[l] + x), max(rev[l], rev[l] + x)) >= r - l; }, 0, 1 + int(str.size()) - 1 - rev[l]);
            ll cnt = rs - (-ls) + 1;
            res += cnt * (cnt - 1) / 2;
        }
        return res;
    };

    ll ans = 0;
    ans += count_palindrome_pairs(s + "/@" + t);  // 区切り文字を中心とする回文ができないように適当な記号2つで区切る
    ans -= count_palindrome_pairs(s);
    ans -= count_palindrome_pairs(t);

    cout << ans << '\n';
}
0