#796776 (C++17) No.599 回文かい

提出ソース
結果

問題	No.599 回文かい
ユーザー	cutmdo
提出日時	2022-09-13 03:53:21
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	2,277 ms / 4,000 ms
コード長	13,651 bytes
コンパイル時間	1,639 ms
コンパイル使用メモリ	129,476 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-05-07 13:22:15
合計ジャッジ時間	17,175 ms
ジャッジサーバーID （参考情報）	judge4 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	5 ms 5,376 KB
testcase_05	AC	4 ms 5,376 KB
testcase_06	AC	4 ms 5,376 KB
testcase_07	AC	5 ms 5,376 KB
testcase_08	AC	5 ms 5,376 KB
testcase_09	AC	4 ms 5,376 KB
testcase_10	AC	1,164 ms 5,376 KB
testcase_11	AC	691 ms 5,376 KB
testcase_12	AC	1,344 ms 5,376 KB
testcase_13	AC	727 ms 5,376 KB
testcase_14	AC	1,702 ms 5,376 KB
testcase_15	AC	2,181 ms 5,376 KB
testcase_16	AC	2,009 ms 5,376 KB
testcase_17	AC	2,277 ms 5,376 KB
testcase_18	AC	2 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
evil_0.txt	AC	1,430 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define PROBLEM "https://yukicoder.me/problems/no/599"

#include <iostream>
#include <vector>
#include <deque>
#include <utility>
#include <list>
#include <string>
#include <set>
#include <unordered_map>

template <class Lambda>
auto binarySearch(long long mn, long long mx, const Lambda& judge, bool rev = false) {
    auto ok = mx;
    auto ng = mn - 1;
    while(ok - ng > 1) {
        auto mid = (ok + ng) / 2;
        auto isOk = judge(mid);
        if((isOk && !rev) || (!isOk && rev)) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    return ok;
}

class SuffixArray {
    enum class TYPE {
        L, S, LMS
    };

    const std::string m_str;
    const std::vector<int> m_suffixArray;

    /* string to vector<int> */
    static std::vector<int> toIntVec(const std::string& str) {
        std::vector<int> vec;
        vec.reserve(str.size() + 1);
        for(const auto& c : str) {
            vec.emplace_back(c - '0' + 1);
        }
        vec.emplace_back(0);
        return vec;
    }

    /* classify { L, S, LMS } */
    static std::vector<TYPE> classifying(const std::vector<int>& str) {
        auto sz = str.size();
        auto typeArray = std::vector<TYPE>(sz);
        typeArray[sz - 1] = TYPE::S;
        for(int i = sz - 2; i >= 0; --i) {
            if(str[i] == str[i + 1]) {
                typeArray[i] = typeArray[i + 1];
                continue;
            }
            typeArray[i] = (str[i] < str[i + 1]) ? TYPE::S : TYPE::L;
        }
        for(int i = 1; i < sz; ++i) {
            if(typeArray[i - 1] == TYPE::L && typeArray[i] == TYPE::S) {
                typeArray[i] = TYPE::LMS;
            }
        }
        return typeArray;
    }

    /* induced sort */
    static std::vector<int> inducedSort(const std::vector<int>& str, const std::vector<TYPE>& type, std::list<int>& lmsList) {
        auto sz = str.size();
        auto nList = std::set<int>();
        for(const auto& c : str) { nList.emplace(c); }

        auto befCheck = [&](int k, auto& addList, bool rev) {
            if(k == 0) { return; }
            if(!rev && type[k - 1] == TYPE::L) {
                addList[str[k - 1]].emplace_back(k - 1);
            }
            if(rev && type[k - 1] != TYPE::L) {
                addList[str[k - 1]].emplace_front(k - 1);
            }
        };

        auto checkAndUpdate = [&](int n, auto& checkList, auto& addList, bool rev) {
            auto& lst = checkList[n];
            if(rev) {
                for(auto itr = lst.rbegin(); itr != lst.rend(); ++itr) { befCheck(*itr, addList, rev); }
            } else {
                for(const auto& k : lst) { befCheck(k, addList, rev); }
            }
        };

        /* set LMS */
        auto tailList = std::unordered_map<int, std::list<int>>();
        for(const auto& i : lmsList) { tailList[str[i]].emplace_back(i); }

        /* set L-type */
        auto headList = std::unordered_map<int, std::list<int>>();
        for(const auto& n : nList) {
            checkAndUpdate(n, headList, headList, false);
            checkAndUpdate(n, tailList, headList, false);
        }

        /* set S-type*/
        tailList = std::unordered_map<int, std::list<int>>();
        for(auto itr_n = nList.rbegin(); itr_n != nList.rend(); ++itr_n) {
            auto n = *itr_n;
            checkAndUpdate(n, tailList, tailList, true);
            checkAndUpdate(n, headList, tailList, true);
        }

        /* merge */
        auto suffixArray = std::vector<int>();
        suffixArray.reserve(sz);
        for(const auto& n : nList) {
            for(const auto& c : headList[n]) { suffixArray.emplace_back(c); }
            for(const auto& c : tailList[n]) { suffixArray.emplace_back(c); }
        }

        return suffixArray;
    }

    /* order lms -> sorted lms */
    static std::unordered_map<int, int> getLmsChanger(const std::vector<int>& str, const std::vector<TYPE>& type, const std::list<int>& lms) {
        if(lms.size() == 1) { return std::unordered_map<int, int>{ { str.size() - 1, 0 }}; }
        std::unordered_map<int, int> changer{{static_cast<int>(str.size()) - 1,0},{*++lms.begin(),1}};
        int num = 1;
        for(auto itr = ++lms.begin(); itr != (--lms.end());) {
            auto f1 = *itr;
            auto f2 = *(++itr);

            bool isSame = false;
            for(int i = 0;; ++i) {
                if(str[f1 + i] != str[f2 + i]) { break; }
                auto b1 = (type[f1 + i] == TYPE::LMS);
                auto b2 = (type[f2 + i] == TYPE::LMS);
                if((b1 || b2) && i > 0) {
                    if(b1 && b2) { isSame = true; break; }
                    break;
                }
            }
            if(!isSame) { ++num; }
            changer.emplace(f2, num);
        }
        return changer;
    }

    /* calc Suffix Array*/
    static std::vector<int> constructSuffixArray(const std::vector<int>& str) {
        auto type = classifying(str);

        /* calc fake Suffix Array using order seed*/
        auto lmsOrder = [&type]() {
            auto lms = std::list<int>();
            for(int i = 0; i < type.size(); ++i) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
            return lms;
        }();
        auto fakeArray = inducedSort(str, type, lmsOrder);

        /* calc true seed */
        auto lmsFakeOrder = [&fakeArray, &type]() {
            auto lms = std::list<int>();
            lms.emplace_back(static_cast<int>(type.size()) - 1);
            for(const auto& i : fakeArray) if(type[i] == TYPE::LMS) { lms.emplace_back(i); }
            return lms;
        }();
        auto changer = getLmsChanger(str, type, lmsFakeOrder);
        auto& lmsTrueOrder = lmsFakeOrder;
        if(changer[*lmsFakeOrder.rbegin()] + 1 < lmsFakeOrder.size()) {
            /* exist same lms-substring */
            auto str = std::vector<int>();
            auto def = std::vector<int>();
            str.reserve(lmsOrder.size());
            def.reserve(lmsOrder.size());
            for(const auto& c : lmsOrder) {
                str.emplace_back(changer[c]);
                def.emplace_back(c);
            }
            auto lmsSuffixArray = constructSuffixArray(str);
            lmsTrueOrder = std::list<int>{static_cast<int>(type.size()) - 1};
            for(const auto& c : lmsSuffixArray) {
                lmsTrueOrder.emplace_back(def[c]);
            }
        }

        /* calc true Suffix Array using true seed */
        auto suffixArray = inducedSort(str, type, lmsTrueOrder);

        return suffixArray;
    }

public:
    SuffixArray(const std::string& str) :m_str(str), m_suffixArray(constructSuffixArray(toIntVec(str))) {}

    /**
     * 引数として与えられたpattern出現位置の区間を返す
     */
    std::pair<int, int> findPattern(const std::string& pattern) const {

        auto find = [&](const std::string& ptn) {
            int end = m_suffixArray.size();
            int ptn_sz = ptn.size();
            auto ret = binarySearch(0, end, [&](int mid) {
                int st = m_suffixArray[mid];
                int sub_sz = end - st;
                for(int k = 0; k < std::min(ptn_sz, sub_sz); ++k) {
                    if(ptn[k] < m_str[st + k]) { return true; }
                    if(ptn[k] > m_str[st + k]) { return false; }
                }
                return ptn_sz <= sub_sz;
            });
            return ret;
        };
        auto patternUpper = [&pattern]() {
            auto ptn = pattern;
            ++* ptn.rbegin();
            return ptn;
        }();
        auto fl = find(pattern);
        auto fu = find(patternUpper);
        return {fl,fu};
    }

    auto getSuffixArray() const {
        return m_suffixArray;
    }

    /* output fot debug */
    void debugOutput() const {
        for(const auto& x : m_suffixArray) {
            std::cout << x << " ";
        }std::cout << std::endl;
        auto end = m_str.size();
        for(const auto& x : m_suffixArray) {
            std::cout << m_str.substr(x, end) << std::endl;
        }
    }
};

class LCPArray {

    const std::vector<int> m_lcpArray;
    const std::vector<int> m_suffixArray;

    static std::vector<int> constructLcpArray(const std::string& str) {
        auto sz = str.size();
        const auto suffixArray = SuffixArray(str).getSuffixArray();

        auto rank = std::vector<int>(sz);
        for(int i = 0; i < sz; ++i) { rank[suffixArray[i]] = i; }

        auto lcpArray = std::vector<int>(sz - 1);
        for(int i = 0, h = 0; i < sz; ++i) {
            if(rank[i] == 0) { continue; }
            int j = suffixArray[rank[i] - 1];
            if(h > 0) { --h; }
            for(; j + h < sz && i + h < sz; ++h) {
                if(str[i + h] != str[j + h]) { break; }
            }
            lcpArray[rank[i] - 1] = h;
        }
        return lcpArray;
    }

public:
    LCPArray(const std::string& str) :
        m_suffixArray(SuffixArray(str).getSuffixArray()),
        m_lcpArray(constructLcpArray(str)) {
    }

    auto getLCPArray()const { return m_lcpArray; }
    auto getSuffixArrayIndexList()const {
        std::vector<int> sail(m_suffixArray.size());
        for(unsigned int i = 0; i < m_suffixArray.size(); ++i) {
            sail[m_suffixArray[i]] = i;
        }
        return sail;
    }
}; 

template<class T>
class isMonoid {
    template <class U>
    static auto check(U x) -> decltype(x.binaryOperation(x), std::true_type{});
    static std::false_type check(...);
public:
    static bool const value = decltype(check(std::declval<T>()))::value;
};

template<class Monoid, std::enable_if_t<isMonoid<Monoid>::value, std::nullptr_t> = nullptr >
class SegmentTree {
private:
    const int m_size;
    std::vector<Monoid> m_node;
    using S = decltype(Monoid().m_val);

    int calcSize(int n) const { int size = 1; while(size < n) { size <<= 1; }return size; }

    template<class Lambda>
    auto _update_op(int itr, Monoid&& val, const Lambda& op) {
        int i = itr + m_size - 1;
        m_node[i] = op(m_node[i], std::forward<decltype(val)>(val));
        while(i) {
            i = (i - 1) >> 1;
            m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
        }
    }

    auto _query(int _l, int _r) const {
        _l = std::max(_l, 0); _r = std::min(_r, m_size - 1);
        auto l = _l + m_size;
        int r = _r + m_size;
        std::deque<Monoid> ldq, rdq;
        while(l <= r) {
            if(l & 1) { ldq.emplace_back(m_node[l - 1]); ++l; }
            if(!(r & 1)) { rdq.emplace_front(m_node[r - 1]); --r; }
            l >>= 1, r >>= 1;
        }
        auto res = Monoid();
        for(auto&& m : ldq) { res = res.binaryOperation(m); }
        for(auto&& m : rdq) { res = res.binaryOperation(m); }
        return res;
    }

    auto _construct(const std::vector<S>& vec) {
        for(unsigned int i = 0; i < vec.size(); ++i) {
            m_node[i + m_size - 1] = Monoid(vec[i]);
        }
        for(int i = m_size - 2; i >= 0; --i) {
            m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
        }
    }
public:
    SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {}
    SegmentTree(int n, const std::vector<S>& vec) :SegmentTree(n) { _construct(vec); }

    template<class Lambda>
    auto update_op(int itr, Monoid&& val, const Lambda& op) { return _update_op(itr, std::forward<Monoid>(val), op); }
    auto update(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid&, const Monoid& m2) {return m2; }); }
    auto add(int itr, Monoid&& val) { return update_op(itr, std::forward<Monoid>(val), [](const Monoid& m1, const Monoid& m2) {return Monoid(m1.m_val + m2.m_val); }); }
    auto query(int l, int r)const { return _query(l, r).m_val; }

    auto output()const {
        for(int i = 0; i < m_size; ++i) { std::cout << m_node[m_size + i - 1] << " "; }
        std::cout << std::endl;
    }
};


template<
    class S,   // 要素の型
    S element, // 元
    class T // lambdaはC++20じゃないと渡せなかった．．．
    // S T(S, S)  // 2項演算子
>
struct Monoid {
    S m_val;
    Monoid() :m_val(element) {}
    Monoid(S val) :m_val(val) {}
    Monoid binaryOperation(const Monoid& m2)const { return T()(m_val, m2.m_val); }
    friend std::ostream& operator<<(std::ostream& os, const Monoid<S, element, T>& m) {
        return os << m.m_val;
    }
};

using ll = long long;
using std::cout;
using std::cin;
constexpr char endl = '\n';
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;

struct F { auto operator()(int a, int b)const { return std::min(a, b); }; };
using M = Monoid<int, static_cast<int>(1e9), F>;

constexpr ll MOD = 1000000007;

signed main() {
    std::string s;
    cin >> s;

    ll size = s.size();
    auto lcparray = LCPArray(s);
    auto segtree = SegmentTree<M>(size, lcparray.getLCPArray());
    auto sai = lcparray.getSuffixArrayIndexList();

    ll half = (size >> 1);
    std::vector<ll> dp(half + 1);
    dp[0] = 1;
    for(int l = 0; l < half; ++l) {
        for(int r = l; r < half; ++r) {

            auto idx1 = sai[l];
            auto idx2 = sai[size - r - 1];
            if(idx2 < idx1) { std::swap(idx1, idx2); }
            auto lcp = segtree.query(idx1, idx2 - 1);

            int len = r - l + 1;
            if(lcp >= len) {
                dp[r + 1] += dp[l];
                if(dp[r + 1] >= MOD) { dp[r + 1] -= MOD; }
            }
        }
    }

    ll ans = 0;
    for(const auto& x : dp) { ans += x; if(ans >= MOD) { ans -= MOD; } }
    cout << ans << endl;
}