#define PROBLEM "https://yukicoder.me/problems/no/263" #include #include #include #include #include #include namespace suisen { namespace internal::palindromic_tree { template constexpr bool false_v = false; template struct PalindromicTreeBase { using container_type = Sequence; using value_type = T; using children_container_type = ChildrenContainerType; struct PalindromicTreeNode { friend struct PalindromicTreeBase; PalindromicTreeNode() = default; private: children_container_type _children; int _suffix_link; int _length; int _multiplicity; int _first_occurence; }; using node_type = PalindromicTreeNode; using node_pointer_type = node_type*; static constexpr int NODE_NULL = -1; static constexpr int NODE_M1 = 0; static constexpr int NODE_0 = 1; PalindromicTreeBase() { node_pointer_type node_m1 = _new_node(); node_m1->_suffix_link = NODE_M1; node_m1->_length = -1; node_m1->_first_occurence = 1; node_pointer_type node_0 = _new_node(); node_0->_suffix_link = NODE_M1; node_0->_length = 0; node_m1->_first_occurence = 0; _active_index = 0; } template PalindromicTreeBase(const Iterable& seq) : PalindromicTreeBase() { add_all(seq); } void add(const value_type& val) { _seq.push_back(val); node_pointer_type par_node = _find_next_longest_suffix_palindrome(_get_node(_active_index)); auto& ch = par_node->_children; bool inserted = false; if constexpr (is_map) { const auto [it, inserted_tmp] = ch.emplace(val, _nodes.size()); inserted = inserted_tmp; _active_index = it->second; } else if constexpr (is_vector) { if (value_type(ch.size()) <= val) ch.resize(val + 1, NODE_NULL); if (ch[val] == NODE_NULL) { inserted = true; ch[val] = _nodes.size(); _active_index = _nodes.size(); } else { _active_index = ch[val]; } } else if constexpr (is_array) { if (ch[val] == NODE_NULL) { inserted = true; ch[val] = _nodes.size(); _active_index = _nodes.size(); } else { _active_index = ch[val]; } } else static_assert(false_v); if (not inserted) { ++_get_node(_active_index)->_multiplicity; return; } int par_length = par_node->_length; int par_suffix_link = par_node->_suffix_link; node_pointer_type new_node = _new_node(); new_node->_multiplicity = 1; new_node->_length = par_length + 2; new_node->_first_occurence = _seq.size() - new_node->_length; if (new_node->_length == 1) { new_node->_suffix_link = NODE_0; } else { new_node->_suffix_link = _find_next_longest_suffix_palindrome(_get_node(par_suffix_link))->_children[val]; } } template void add_all(const Iterable &seq) { for (const auto &val : seq) add(val); } int node_num() const { return _nodes.size(); } const node_type& get_node(int index) const { return _nodes[index]; } int first_occurence(int index) const { return get_node(index)._first_occurence; } int length(int index) const { return get_node(index)._length; } int suffix_link(int index) const { return get_node(index)._suffix_link; } int node_multiplicity(int index) const { return get_node(index)._multiplicity; } const children_container_type& children(int index) const { return get_node(index)._children; } std::vector parents() const { int sz = node_num(); std::vector res(sz, -1); for (int i = 0; i < sz; ++i) { for (const auto& p : children(i)) { if constexpr (is_map) { res[p.second] = i; } else if (p != NODE_NULL) { res[p] = i; } } } return res; } const container_type get_palindrome(int index) { if (index == NODE_M1) return container_type{}; int l = first_occurence(index), r = l + length(index); return container_type{ _seq.begin() + l, _seq.begin() + r }; } std::vector frequency_table() const { int sz = node_num(); std::vector res(sz); for (int i = sz; i-- > 1;) { res[i] += node_multiplicity(i); res[suffix_link(i)] += res[i]; } return res; } void clear() { _active_index = 0; _seq.clear(); _seq.shrink_to_fit(); _nodes.clear(); _nodes.shrink_to_fit(); } private: static constexpr bool is_map = std::is_same_v, children_container_type>; static constexpr bool is_vector = std::is_same_v, children_container_type>; static constexpr bool is_array = std::is_same_v>, children_container_type>; int _active_index; container_type _seq; std::vector _nodes; node_pointer_type _new_node() { node_pointer_type new_node = &_nodes.emplace_back(); if constexpr (not (is_map or is_vector)) { std::fill(new_node->_children.begin(), new_node->_children.end(), NODE_NULL); } return new_node; } node_pointer_type _find_next_longest_suffix_palindrome(node_pointer_type node) { const int sz = _seq.size(); for (;; node = _get_node(node->_suffix_link)) { int opposite_index = sz - node->_length - 2; if (opposite_index >= 0 and _seq[opposite_index] == _seq.back()) return node; } } node_pointer_type _get_node(int index) { return &_nodes[index]; } }; } // namespace internal::palindromic_tree template > struct PalindromicTree : public internal::palindromic_tree::PalindromicTreeBase> { using base_type = internal::palindromic_tree::PalindromicTreeBase>; using base_type::base_type; }; template > struct PalindromicTreeVec : public internal::palindromic_tree::PalindromicTreeBase> { using base_type = internal::palindromic_tree::PalindromicTreeBase>; using base_type::base_type; }; template > struct PalindromicTreeArr : public internal::palindromic_tree::PalindromicTreeBase> { using base_type = internal::palindromic_tree::PalindromicTreeBase>; using base_type::base_type; }; } // namespace suisen using suisen::PalindromicTree; int main() { std::string s, t; std::cin >> s >> t; PalindromicTree tree(s); std::vector f = tree.frequency_table(); tree.add('['), tree.add(']'); tree.add_all(t); std::vector g = tree.frequency_table(); long long ans = 0; for (int i = 2, n = f.size(); i < n; ++i) { ans += (long long) f[i] * (g[i] - f[i]); } std::cout << ans << std::endl; // verification of other versions of palindromic tree { using suisen::PalindromicTreeVec; using suisen::PalindromicTreeArr; auto fix = [](const std::string& s) { std::vector res; for (char c : s) res.push_back(c - 'A'); return res; }; PalindromicTreeVec tv(fix(s)); assert(tv.frequency_table() == f); tv.add(26), tv.add(27); tv.add_all(fix(t)); assert(tv.frequency_table() == g); tv.clear(); PalindromicTreeArr ta(fix(s)); assert(ta.frequency_table() == f); ta.add(26), ta.add(27); ta.add_all(fix(t)); assert(ta.frequency_table() == g); } return 0; }