#820932 (C++17) No.263 Common Palindromes Extra

• 問題: No.263 Common Palindromes Extra
• ユーザー: cutmdo
• 提出日時: 2022-12-01 01:14:33
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: MLE
• 実行時間: -
• コード長: 7,723 bytes
• コンパイル時間: 1,921 ms
• コンパイル使用メモリ: 133,896 KB
• 実行使用メモリ: 396,440 KB
• 最終ジャッジ日時: 2024-10-07 20:35:20
• 合計ジャッジ時間: 7,891 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	29 ms; 9,856 KB
testcase_01	AC	2 ms; 6,820 KB
testcase_02	AC	2 ms; 6,816 KB
testcase_03	AC	73 ms; 21,008 KB
testcase_04	AC	493 ms; 89,996 KB
testcase_05	AC	523 ms; 88,932 KB
testcase_06	AC	33 ms; 11,776 KB
testcase_07	AC	569 ms; 173,624 KB
testcase_08	AC	598 ms; 173,108 KB
testcase_09	MLE	-
testcase_10	MLE	-
testcase_11	AC	336 ms; 88,080 KB

ソースコード

#include <iostream>
#include <algorithm>

#include <memory>
#include <string>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <unordered_map>

auto nullLambda = [](int, const std::list<int>&) {};
class PalindromicTree {
    //static constexpr auto nullLambda = [](int, const std::list<int>&) {};// c++17

    class Node :public std::enable_shared_from_this<Node> {
        // 回文の右端itr
        std::list<int> m_itrs;
        // 回文サイズ
        const int m_size;

        // 最大の回文接尾辞
        std::weak_ptr<Node> m_suffixLink;
        // 次サイズの回文(囲む文字, 次のNode)
        std::unordered_map<char, std::shared_ptr<Node>> m_edges;


        // xAxとなるAを探す(x=str[itr])
        auto find(int itr, const std::string& s, bool flg = false) {
            auto p = this->weak_from_this();
            while(true) {
                auto size = p.lock()->m_size;
                // rootにたどり着いた
                if(size == -1) { return p; }
                // 現在地"A"において"xAx"となる
                if(itr - size - 1 >= 0 && s[itr] == s[itr - size - 1]) {
                    return p;
                }
                p = p.lock()->m_suffixLink;
            }
        }

        // 新しい回文Nodeを作成する
        auto create(int itr, const std::string& s) {
            // suffixLinkの探索
            auto suffixLinkFrom = m_suffixLink.lock()/*->m_suffixLink.lock()*/->find(itr, s, true).lock();
            // 新Nodeの作成
            auto newNode = std::make_shared<Node>(
                m_size + 2, (suffixLinkFrom->m_edges.find(s[itr]) == suffixLinkFrom->m_edges.end()) ?
                suffixLinkFrom->m_edges.find(' ')->second :
                suffixLinkFrom->m_edges.find(s[itr])->second);
            m_edges.emplace(s[itr], newNode);
            return std::weak_ptr<Node>(newNode);
        }

    public:
        // constructor
        Node(int size, const std::weak_ptr<Node>& suffixLink) :
            m_size(size),
            m_suffixLink(suffixLink) {
        }
        Node() :m_size(-1) {}


        // 次サイズの回文を追加
        auto add(int itr, const std::string& s) {
            auto addRoot = find(itr, s).lock();
            auto nextNode = (addRoot->m_edges.find(s[itr]) == addRoot->m_edges.end()) ?
                addRoot->create(itr, s) :
                std::weak_ptr<Node>(addRoot->m_edges.find(s[itr])->second);
            nextNode.lock()->m_itrs.emplace_back(itr);
            return nextNode;
        }

        // debug用
        auto outputTree(const std::string& s) ->void const {
            if(m_size <= 0) { std::cerr << "root"; } else {
                // 段
                for(int i = 0; (i < (m_size + 1) / 2); ++i) { std::cerr << " |"; }
                std::cerr << "- " << s.substr(*m_itrs.begin() - m_size + 1, m_size);
                // 右itr
                std::cerr << " [ "; for(const auto& itr : m_itrs) { std::cerr << itr << " "; }std::cerr << "] ";
                // suffix link
                //auto p = m_suffixLink.lock();
                //std::cerr << "{" << s.substr(*p->m_itrs.begin() - p->m_size + 1, p->m_size) << "} ";
            } std::cerr << "\n";
            for(const auto& edge : m_edges) {
                if(m_size == -1 && edge.first == ' ') { continue; }
                edge.second->outputTree(s);
            }
        }

        // rootを決定
        auto isOddRoot(const std::weak_ptr<Node>& evenRoot) {
            m_suffixLink = weak_from_this();
            m_edges.emplace(' ', evenRoot);
        }

        // ラムダ式の実行
        template<class Lambda>
        auto runLambda(const Lambda& lambda) {
            if(m_size > 0) { lambda(m_size, m_itrs); }
        }

        /*
         * lambda: (int size, list<int> rItr) -> void
         */
        template<class Lambda, class SuffixLinkLambda = decltype(nullLambda)>
        auto dfs_edges(const Lambda& lambda, const SuffixLinkLambda& slLambda = nullLambda)->void {
            std::stack<std::shared_ptr<Node>, std::list<std::shared_ptr<Node>>> stk;
            stk.emplace(this->weak_from_this().lock());
            while(!stk.empty()) {
                auto p = stk.top();
                stk.pop();
                p->runLambda(lambda);
                p->m_suffixLink.lock()->runLambda(slLambda);
                for(const auto& [_, next_p] : p->m_edges) {
                    // std::cerr << p->m_size << " -> " << next_p->m_size << std::endl;
                    stk.emplace(next_p);
                }
            }
        }
    };

    // 対象となる文字列
    const std::string m_s;

    // 偶数長，奇数長のPalindromicTreeの根(0, -1)
    std::shared_ptr<Node> m_rootOdd;
    std::shared_ptr<Node> m_rootEven;
public:
    // constructor
    PalindromicTree(const std::string& s) :
        m_s(s),
        m_rootOdd(std::make_shared<Node>()),
        m_rootEven(std::make_shared<Node>(0, m_rootOdd)) {
        m_rootOdd->isOddRoot(m_rootEven);
        auto root = m_rootOdd;
        for(int r = 0; r < static_cast<int>(s.size()); ++r) {
            root = root->add(r, s).lock();
        }
    }

    /*
     * lambda: (int size, list<int> rItr) -> void
     */
    template<class Lambda>
    auto dfs_edges(const Lambda& lambda) {
        m_rootOdd->dfs_edges(lambda);
    }

    /*
     * かなり強引な実装
     * lambda: (int from, int to) -> void
     */
    template<class Lambda>
    auto dp_suffixLink(const Lambda& lambda) {
        // 森の生成，探索順序の決定
        int from;
        std::unordered_map<int, int> graph;
        std::vector<int> orderCount(m_s.size());
        m_rootOdd->dfs_edges([&](int size, const std::list<int>& rItrs) {
            from = rItrs.front();
        }, [&](int size, const std::list<int>& rItrs) {
            int to = rItrs.front();
            graph.emplace(from, to);
            ++orderCount[to];
        });
        // 探索順序に従って処理
        std::queue<int, std::list<int>> q;
        for(int i = 0; i < static_cast<int>(m_s.size()); ++i)if(orderCount[i] == 0) { q.emplace(i); }
        while(!q.empty()) {
            int from = q.front();
            q.pop();
            auto range = graph.equal_range(from);
            for(auto itr = range.first; itr != range.second; ++itr) {
                int to = itr->second;
                --orderCount[to];
                lambda(from, to);
                if(orderCount[to] == 0) { q.emplace(to); }
            }
        }
    }

    // debug用
    auto outputTree() {
        std::cerr << m_s << std::endl;
        std::cerr << "-- even --\n";
        m_rootEven->outputTree(m_s);
        std::cerr << "-- odd --\n";
        m_rootOdd->outputTree(m_s);
    }
};
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;

signed main() {
    std::string a, b;
    cin >> a >> b;
    std::string s = a + "$%" + b;

    auto tree = PalindromicTree(s);

    ll an = a.size();
    std::vector<std::pair<ll, ll>> dp(s.size());
    tree.dfs_edges([&](int size, const std::list<int>& ritr) {
        ll l = 0, r = 0;
        for(const auto& x : ritr) if(x != an && x != an + 1) {
            ++((x < an) ? l : r);
        }
        dp[ritr.front()] = {l,r};
    });

    tree.dp_suffixLink([&](int from, int to) {
        dp[to].first += dp[from].first;
        dp[to].second += dp[from].second;
    });

    ll ans = 0;
    for(const auto& p : dp) { ans += (p.first * p.second); }
    cout << ans << endl;
}