結果

問題 No.273 回文分解
ユーザー cutmdo
提出日時 2020-01-06 20:59:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 7,085 bytes
コンパイル時間 1,988 ms
コンパイル使用メモリ 140,236 KB
最終ジャッジ日時 2025-01-08 16:26:54
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>
#include <bitset>
#include <numeric>
#include <cassert>
#include <array>
#include <memory>
#ifdef DEBUG
#include "./Lib/debug.hpp"
#include "./Lib/Timer.hpp"
#include "./Lib/sample.hpp"
#else
#define dump(...)
#endif
/* (=＾o＾=) */
#define int ll
/* macro */
#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define REPI2(it,b,e) for(auto it = (b); it != (e); ++it)
#define REPI(it,c) REPI2(it, (c).begin(), (c).end())
#define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend())
#define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);)
#define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end())
#define ALL(x) (x).begin(),(x).end()
#define cauto const auto&
/* macro func */
template<class T>
inline auto sort(T& t) { std::sort(ALL(t)); }
template<class T>
inline auto rsort(T& t) { std::sort((t).rbegin(), (t).rend()); }
template<class T>
inline auto unique(T& t) { (t).erase(unique((t).begin(), (t).end()), (t).end()); }
template<class T, class S>
inline auto chmax(T& t, const S& s) { if (s > t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmaxE(T& t, const S& s) { if (s >= t) { t = s; return true; } return false; }
template<class T, class S>
inline auto chmin(T& t, const S& s) { if (s < t) { t = s; return true; } return false; }
inline auto BR() { std::cout << "\n"; }
/* type define */
using ll = long long;
using PAIR = std::pair<ll, ll>;
using VS = std::vector<std::string>;
using VL = std::vector<long long>;
using VVL = std::vector<VL>;
using VVVL = std::vector<VVL>;
using VD = std::vector<double>;
template<class T>
using V = std::vector<T>;
/* using std */
using std::cout;
constexpr char endl = '\n';
using std::cin;
using std::pair;
using std::string;
using std::stack;
using std::queue;
using std::vector;
using std::list;
using std::map;
using std::unordered_map;
using std::multimap;
using std::unordered_multimap;
using std::set;
using std::unordered_set;
using std::unordered_multiset;
using std::multiset;
using std::bitset;
using std::priority_queue;
/* constant value */
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
/* Initial processing  */
struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing;
/* Remove the source of the bug */
inline signed pow(signed, signed) { assert(false); return -1; }
/* define hash */
namespace std {
template <> class hash<std::pair<ll, ll>> { public: size_t operator()(const std::pair<ll, ll>& x) const { return hash<ll>()(1000000000 * x.first + x
    .second); } };
}
/* input */
template<class T> std::istream& operator >> (std::istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
//=============================================================================================
class PalindromicTree {
    class Node :public std::enable_shared_from_this<Node> {
        // 最大の回文接尾辞
        std::weak_ptr<Node> m_suffixLink;
        // 次サイズの回文(囲む文字, 次のNode)
        std::unordered_map<char, std::shared_ptr<Node>> m_edges;
        // 回文の右端itr
        std::list<int> m_itrs;
        // 回文サイズ
        const int m_size;
        // xAxとなるAを探す(x=str[itr])
        auto find(int itr, const std::string& s, bool flg = false) {
            // rootにたどり着いた
            if (m_size == -1) { return weak_from_this(); }
            // 現在地"A"において"xAx"となる
            if (itr - m_size - 1 >= 0 && s[itr] == s[itr - m_size - 1]) {
                return weak_from_this();
            }
            // 見つからない
            return m_suffixLink.lock()->find(itr, s, flg);
        }
        // 新しい回文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 {
            if (m_size <= 0) { cout << "root"; } else {
                // 段
                for (int i = 0; (i < (m_size + 1) / 2); ++i) { cout << " |"; }
                cout << "- " << s.substr(*m_itrs.begin() - m_size + 1, m_size);
                // 右itr
                cout << " [ "; for (const auto& itr : m_itrs) { cout << itr << " "; }cout << "] ";
                // suffix link
                //auto p = m_suffixLink.lock();
                //cout << "{" << s.substr(*p->m_itrs.begin() - p->m_size + 1, p->m_size) << "} ";
            } cout << "\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);
        }
        /*
         * lambda: (int size, list<int> rItr) -> void
         */
        template<class Lambda>
        auto dfs_edges(const Lambda& lambda)->void {
            if (m_size > 0) { lambda(m_size, m_itrs); }
            for (const auto& edge : m_edges) {
                edge.second->dfs_edges(lambda);
            }
        }
    };
    // 対象となる文字列
    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 < 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);
    }
    // debug用
    auto outputTree() {
        dump(m_s);
        cout << "-- even --\n";
        m_rootEven->outputTree(m_s);
        cout << "-- odd --\n";
        m_rootOdd->outputTree(m_s);
    }
};
signed main() {
    string s;
    cin >> s;
    auto p = PalindromicTree(s);
    ll ans = 0;
    p.dfs_edges([&](auto a, auto b) {if (a < s.size()) { chmax(ans, a); }});
    cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0