cp-library-cpp
This documentation is automatically generated by online-judge-tools/verification-helper
test/src/string/palindromic_tree/yuki263.test.cpp
- View this file on GitHub
- Last update: 2022-07-05 04:29:34+09:00
- Problem: https://yukicoder.me/problems/no/263
Depends on
Code
#define PROBLEM "https://yukicoder.me/problems/no/263"
#include <iostream>
#include <string>
#include "library/string/palindromic_tree.hpp"
using suisen::PalindromicTree;
int main() {
std::string s, t;
std::cin >> s >> t;
PalindromicTree<char, std::string> tree(s);
std::vector<int> f = tree.frequency_table();
tree.add('['), tree.add(']');
tree.add_all(t);
std::vector<int> 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
{
tree.clear<true>();
tree.shrink_to_fit();
using suisen::PalindromicTreeVec;
using suisen::PalindromicTreeArr;
auto fix = [](const std::string& s) {
std::vector<int> res;
for (char c : s) res.push_back(c - 'A');
return res;
};
PalindromicTreeVec<int> 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<true>();
tv.shrink_to_fit();
PalindromicTreeArr<int, 28> 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;
}#line 1 "test/src/string/palindromic_tree/yuki263.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/263"
#include <iostream>
#include <string>
#line 1 "library/string/palindromic_tree.hpp"
#include <array>
#include <cassert>
#include <vector>
#include <map>
namespace suisen {
namespace internal::palindromic_tree {
template <typename T>
constexpr bool false_v = false;
template <typename T, typename Sequence, typename ChildrenContainerType>
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_0->_first_occurence = 0;
_active_index = 0;
}
template <typename Iterable>
PalindromicTreeBase(const Iterable& seq) : PalindromicTreeBase() {
add_all(seq);
}
int 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<void>);
if (not inserted) {
++_get_node(_active_index)->_multiplicity;
return _active_index;
}
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];
}
return _active_index;
}
template <typename Iterable>
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<int> parents() const {
int sz = node_num();
std::vector<int> 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<int> frequency_table() const {
int sz = node_num();
std::vector<int> res(sz);
for (int i = sz; i-- > 1;) {
res[i] += node_multiplicity(i);
res[suffix_link(i)] += res[i];
}
return res;
}
template <bool erase_root = false>
void clear() {
_active_index = 0;
_seq.clear();
if constexpr (erase_root) {
_nodes.clear();
} else {
_nodes.erase(_nodes.begin() + 2, _nodes.end());
}
}
void shrink_to_fit() {
_seq.shrink_to_fit();
_nodes.shrink_to_fit();
}
private:
static constexpr bool is_map = std::is_same_v<std::map<value_type, int>, children_container_type>;
static constexpr bool is_vector = std::is_same_v<std::vector<value_type>, children_container_type>;
static constexpr bool is_array = std::is_same_v<std::array<value_type, std::tuple_size_v<children_container_type>>, children_container_type>;
int _active_index;
container_type _seq;
std::vector<node_type> _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 <typename T, typename Sequence = std::vector<T>>
struct PalindromicTree : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::map<T, int>>;
using base_type::base_type;
};
template <typename T, typename Sequence = std::vector<T>>
struct PalindromicTreeVec : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::vector<T>>;
using base_type::base_type;
};
template <typename T, std::size_t N, typename Sequence = std::vector<T>>
struct PalindromicTreeArr : public internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>> {
using base_type = internal::palindromic_tree::PalindromicTreeBase<T, Sequence, std::array<T, N>>;
using base_type::base_type;
};
} // namespace suisen
#line 7 "test/src/string/palindromic_tree/yuki263.test.cpp"
using suisen::PalindromicTree;
int main() {
std::string s, t;
std::cin >> s >> t;
PalindromicTree<char, std::string> tree(s);
std::vector<int> f = tree.frequency_table();
tree.add('['), tree.add(']');
tree.add_all(t);
std::vector<int> 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
{
tree.clear<true>();
tree.shrink_to_fit();
using suisen::PalindromicTreeVec;
using suisen::PalindromicTreeArr;
auto fix = [](const std::string& s) {
std::vector<int> res;
for (char c : s) res.push_back(c - 'A');
return res;
};
PalindromicTreeVec<int> 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<true>();
tv.shrink_to_fit();
PalindromicTreeArr<int, 28> 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;
}