deque_palindromic_tree.hpp¶
支持在字符串两端加入字符，并维护不同回文子串与最长回文信息。
Complexity: Time: push O(log n + log sigma) worst case, pop O(log sigma) amortized, and query O(1). Space: O(n), where n is the current length and sigma is the number of distinct ch values.
AC 记录：palindromes_in_deque。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: push O(log n + log sigma) worst case, pop O(log sigma)
/// amortized, and query O(1). Space: O(n), where n is the current length and
/// sigma is the number of distinct ch values.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace deque_palindromic_tree_internal {
template <class T> class amortized_deque {
std::vector<T> l_, r_;
static void move_half(std::vector<T> &t, std::vector<T> &s) {
assert(t.empty() && !s.empty());
std::size_t mov = (s.size() + 1) / 2;
std::move(s.rend() - mov, s.rend(), std::back_inserter(t));
s.erase(s.begin(), s.begin() + mov);
}
public:
int size() const { return int(l_.size() + r_.size()); }
bool empty() const { return l_.empty() && r_.empty(); }
T &operator[](int i) {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
const T &operator[](int i) const {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
T &front() { return l_.empty() ? r_.front() : l_.back(); }
const T &front() const { return l_.empty() ? r_.front() : l_.back(); }
T &back() { return r_.empty() ? l_.front() : r_.back(); }
const T &back() const { return r_.empty() ? l_.front() : r_.back(); }
void push_front(const T &val) { l_.push_back(val); }
void push_front(T &&val) { l_.push_back(std::move(val)); }
void push_back(const T &val) { r_.push_back(val); }
void push_back(T &&val) { r_.push_back(std::move(val)); }
void pop_front() {
assert(!empty());
if (l_.empty()) {
move_half(l_, r_);
}
l_.pop_back();
}
void pop_back() {
assert(!empty());
if (r_.empty()) {
move_half(r_, l_);
}
r_.pop_back();
}
};
} // namespace deque_palindromic_tree_internal
/// @brief Maintain all distinct palindromic substrings under pushes and pops
/// at both ends. Every active palindrome is a node with a suffix link, while
/// each text position stores the longest palindrome beginning or ending there.
/// A quick link skips suffix-link runs whose next extension character is the
/// same, so a new extendable boundary palindrome is found logarithmically.
/// Surface counters and incoming suffix-link counters identify a node exactly
/// when its last occurrence disappears, allowing an end deletion to undo only
/// local certificates. Two reversed vectors provide amortized constant-time
/// deque rebalancing while retaining indexed ch access.
template <class Char = int, class Compare = std::less<Char>>
class deque_palindromic_tree {
struct node {
node *fa = nullptr;
node *lnk = nullptr;
node *ql = nullptr;
std::map<Char, node *, Compare> nxt;
int len = 0;
int cnt = 0;
int il = 0;
};
struct deque_entry {
Char ch;
node *ps;
node *ss;
};
using text_deque =
deque_palindromic_tree_internal::amortized_deque<deque_entry>;
text_deque s_;
std::unique_ptr<node> odd, er;
int dn = 0;
node *back_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[n - cur->len - 1].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[n - suf->len - 1].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
node *front_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[cur->len].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[suf->len].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
static node *transition(node *u, const Char &ch) {
auto it = u->nxt.find(ch);
assert(it != u->nxt.end());
return it->second;
}
public:
deque_palindromic_tree()
: odd(std::make_unique<node>()), er(std::make_unique<node>()) {
odd->len = -1;
odd->fa = odd->lnk = odd->ql = odd.get();
er->len = 0;
er->fa = er->lnk = er->ql = odd.get();
}
deque_palindromic_tree(const deque_palindromic_tree &) = delete;
deque_palindromic_tree &operator=(const deque_palindromic_tree &) = delete;
deque_palindromic_tree(deque_palindromic_tree &&) = delete;
deque_palindromic_tree &operator=(deque_palindromic_tree &&) = delete;
~deque_palindromic_tree() { clear(); }
int size() const { return s_.size(); }
bool empty() const { return s_.empty(); }
int distinct_palindromes() const { return dn; }
int longest_prefix_palindrome() const {
return empty() ? 0 : s_.front().ps->len;
}
int longest_suffix_palindrome() const {
return empty() ? 0 : s_.back().ss->len;
}
void push_back(const Char &ch) {
node *fa = empty() ? odd.get() : back_appendable(ch, s_.back().ss);
int n = size();
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = back_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_back({ch, er.get(), er.get()});
n++;
if (suf->lnk != odd.get() &&
s_[n - suf->len - 1].ch == s_[n - suf->lnk->len - 1].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_back({ch, er.get(), er.get()});
n++;
crt = old->second;
suf = crt->lnk;
}
s_[n - 1].ss = crt;
s_[n - crt->len].ps = crt;
if (suf->len >= 1 && s_[n - crt->len + suf->len - 1].ss == suf) {
s_[n - crt->len + suf->len - 1].ss = er.get();
}
crt->cnt++;
}
void push_front(const Char &ch) {
node *fa = empty() ? odd.get() : front_appendable(ch, s_.front().ps);
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = front_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_front({ch, er.get(), er.get()});
if (suf->lnk != odd.get() && s_[suf->len].ch == s_[suf->lnk->len].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_front({ch, er.get(), er.get()});
crt = old->second;
suf = crt->lnk;
}
s_[0].ps = crt;
s_[crt->len - 1].ss = crt;
if (suf->len >= 1 && s_[crt->len - suf->len].ps == suf) {
s_[crt->len - suf->len].ps = er.get();
}
crt->cnt++;
}
void pop_back() {
assert(!empty());
node *del = s_.back().ss;
Char ch = s_.back().ch;
node *suf = del->lnk;
int n = size();
if (del->len >= 2 && s_[n - del->len + suf->len - 1].ss->len < suf->len) {
s_[n - del->len + suf->len - 1].ss = suf;
s_[n - del->len].ps = suf;
} else {
s_[n - del->len].ps = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_back();
}
void pop_front() {
assert(!empty());
node *del = s_.front().ps;
Char ch = s_.front().ch;
node *suf = del->lnk;
if (del->len >= 2 && s_[del->len - suf->len].ps->len < suf->len) {
s_[del->len - suf->len].ps = suf;
s_[del->len - 1].ss = suf;
} else {
s_[del->len - 1].ss = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_front();
}
void clear() {
while (!empty()) {
pop_back();
}
}
};
} // namespace noya
#ifndef NOYA_DEQUE_PALINDROMIC_TREE_HPP
#define NOYA_DEQUE_PALINDROMIC_TREE_HPP 1
/// @complexity Time: push O(log n + log sigma) worst case, pop O(log sigma)
/// amortized, and query O(1). Space: O(n), where n is the current length and
/// sigma is the number of distinct ch values.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace deque_palindromic_tree_internal {
template <class T> class amortized_deque {
std::vector<T> l_, r_;
static void move_half(std::vector<T> &t, std::vector<T> &s) {
assert(t.empty() && !s.empty());
std::size_t mov = (s.size() + 1) / 2;
std::move(s.rend() - mov, s.rend(), std::back_inserter(t));
s.erase(s.begin(), s.begin() + mov);
}
public:
int size() const { return int(l_.size() + r_.size()); }
bool empty() const { return l_.empty() && r_.empty(); }
T &operator[](int i) {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
const T &operator[](int i) const {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
T &front() { return l_.empty() ? r_.front() : l_.back(); }
const T &front() const { return l_.empty() ? r_.front() : l_.back(); }
T &back() { return r_.empty() ? l_.front() : r_.back(); }
const T &back() const { return r_.empty() ? l_.front() : r_.back(); }
void push_front(const T &val) { l_.push_back(val); }
void push_front(T &&val) { l_.push_back(std::move(val)); }
void push_back(const T &val) { r_.push_back(val); }
void push_back(T &&val) { r_.push_back(std::move(val)); }
void pop_front() {
assert(!empty());
if (l_.empty()) {
move_half(l_, r_);
}
l_.pop_back();
}
void pop_back() {
assert(!empty());
if (r_.empty()) {
move_half(r_, l_);
}
r_.pop_back();
}
};
} // namespace deque_palindromic_tree_internal
/// @brief Maintain all distinct palindromic substrings under pushes and pops
/// at both ends. Every active palindrome is a node with a suffix link, while
/// each text position stores the longest palindrome beginning or ending there.
/// A quick link skips suffix-link runs whose next extension character is the
/// same, so a new extendable boundary palindrome is found logarithmically.
/// Surface counters and incoming suffix-link counters identify a node exactly
/// when its last occurrence disappears, allowing an end deletion to undo only
/// local certificates. Two reversed vectors provide amortized constant-time
/// deque rebalancing while retaining indexed ch access.
template <class Char = int, class Compare = std::less<Char>>
class deque_palindromic_tree {
struct node {
node *fa = nullptr;
node *lnk = nullptr;
node *ql = nullptr;
std::map<Char, node *, Compare> nxt;
int len = 0;
int cnt = 0;
int il = 0;
};
struct deque_entry {
Char ch;
node *ps;
node *ss;
};
using text_deque =
deque_palindromic_tree_internal::amortized_deque<deque_entry>;
text_deque s_;
std::unique_ptr<node> odd, er;
int dn = 0;
node *back_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[n - cur->len - 1].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[n - suf->len - 1].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
node *front_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[cur->len].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[suf->len].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
static node *transition(node *u, const Char &ch) {
auto it = u->nxt.find(ch);
assert(it != u->nxt.end());
return it->second;
}
public:
deque_palindromic_tree()
: odd(std::make_unique<node>()), er(std::make_unique<node>()) {
odd->len = -1;
odd->fa = odd->lnk = odd->ql = odd.get();
er->len = 0;
er->fa = er->lnk = er->ql = odd.get();
}
deque_palindromic_tree(const deque_palindromic_tree &) = delete;
deque_palindromic_tree &operator=(const deque_palindromic_tree &) = delete;
deque_palindromic_tree(deque_palindromic_tree &&) = delete;
deque_palindromic_tree &operator=(deque_palindromic_tree &&) = delete;
~deque_palindromic_tree() { clear(); }
int size() const { return s_.size(); }
bool empty() const { return s_.empty(); }
int distinct_palindromes() const { return dn; }
int longest_prefix_palindrome() const {
return empty() ? 0 : s_.front().ps->len;
}
int longest_suffix_palindrome() const {
return empty() ? 0 : s_.back().ss->len;
}
void push_back(const Char &ch) {
node *fa = empty() ? odd.get() : back_appendable(ch, s_.back().ss);
int n = size();
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = back_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_back({ch, er.get(), er.get()});
n++;
if (suf->lnk != odd.get() &&
s_[n - suf->len - 1].ch == s_[n - suf->lnk->len - 1].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_back({ch, er.get(), er.get()});
n++;
crt = old->second;
suf = crt->lnk;
}
s_[n - 1].ss = crt;
s_[n - crt->len].ps = crt;
if (suf->len >= 1 && s_[n - crt->len + suf->len - 1].ss == suf) {
s_[n - crt->len + suf->len - 1].ss = er.get();
}
crt->cnt++;
}
void push_front(const Char &ch) {
node *fa = empty() ? odd.get() : front_appendable(ch, s_.front().ps);
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = front_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_front({ch, er.get(), er.get()});
if (suf->lnk != odd.get() && s_[suf->len].ch == s_[suf->lnk->len].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_front({ch, er.get(), er.get()});
crt = old->second;
suf = crt->lnk;
}
s_[0].ps = crt;
s_[crt->len - 1].ss = crt;
if (suf->len >= 1 && s_[crt->len - suf->len].ps == suf) {
s_[crt->len - suf->len].ps = er.get();
}
crt->cnt++;
}
void pop_back() {
assert(!empty());
node *del = s_.back().ss;
Char ch = s_.back().ch;
node *suf = del->lnk;
int n = size();
if (del->len >= 2 && s_[n - del->len + suf->len - 1].ss->len < suf->len) {
s_[n - del->len + suf->len - 1].ss = suf;
s_[n - del->len].ps = suf;
} else {
s_[n - del->len].ps = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_back();
}
void pop_front() {
assert(!empty());
node *del = s_.front().ps;
Char ch = s_.front().ch;
node *suf = del->lnk;
if (del->len >= 2 && s_[del->len - suf->len].ps->len < suf->len) {
s_[del->len - suf->len].ps = suf;
s_[del->len - 1].ss = suf;
} else {
s_[del->len - 1].ss = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_front();
}
void clear() {
while (!empty()) {
pop_back();
}
}
};
} // namespace noya
#endif // NOYA_DEQUE_PALINDROMIC_TREE_HPP
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <utility>
#include <vector>
/// @complexity Time: push O(log n + log sigma) worst case, pop O(log sigma)
/// amortized, and query O(1). Space: O(n), where n is the current length and
/// sigma is the number of distinct ch values.
namespace noya {
namespace deque_palindromic_tree_internal {
template <class T> class amortized_deque {
std::vector<T> l_, r_;
static void move_half(std::vector<T> &t, std::vector<T> &s) {
assert(t.empty() && !s.empty());
std::size_t mov = (s.size() + 1) / 2;
std::move(s.rend() - mov, s.rend(), std::back_inserter(t));
s.erase(s.begin(), s.begin() + mov);
}
public:
int size() const { return int(l_.size() + r_.size()); }
bool empty() const { return l_.empty() && r_.empty(); }
T &operator[](int i) {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
const T &operator[](int i) const {
assert(0 <= i && i < size());
return i < int(l_.size()) ? l_[l_.size() - 1 - std::size_t(i)]
: r_[std::size_t(i) - l_.size()];
}
T &front() { return l_.empty() ? r_.front() : l_.back(); }
const T &front() const { return l_.empty() ? r_.front() : l_.back(); }
T &back() { return r_.empty() ? l_.front() : r_.back(); }
const T &back() const { return r_.empty() ? l_.front() : r_.back(); }
void push_front(const T &val) { l_.push_back(val); }
void push_front(T &&val) { l_.push_back(std::move(val)); }
void push_back(const T &val) { r_.push_back(val); }
void push_back(T &&val) { r_.push_back(std::move(val)); }
void pop_front() {
assert(!empty());
if (l_.empty()) {
move_half(l_, r_);
}
l_.pop_back();
}
void pop_back() {
assert(!empty());
if (r_.empty()) {
move_half(r_, l_);
}
r_.pop_back();
}
};
} // namespace deque_palindromic_tree_internal
/// @brief Maintain all distinct palindromic substrings under pushes and pops
/// at both ends. Every active palindrome is a node with a suffix link, while
/// each text position stores the longest palindrome beginning or ending there.
/// A quick link skips suffix-link runs whose next extension character is the
/// same, so a new extendable boundary palindrome is found logarithmically.
/// Surface counters and incoming suffix-link counters identify a node exactly
/// when its last occurrence disappears, allowing an end deletion to undo only
/// local certificates. Two reversed vectors provide amortized constant-time
/// deque rebalancing while retaining indexed ch access.
template <class Char = int, class Compare = std::less<Char>>
class deque_palindromic_tree {
struct node {
node *fa = nullptr;
node *lnk = nullptr;
node *ql = nullptr;
std::map<Char, node *, Compare> nxt;
int len = 0;
int cnt = 0;
int il = 0;
};
struct deque_entry {
Char ch;
node *ps;
node *ss;
};
using text_deque =
deque_palindromic_tree_internal::amortized_deque<deque_entry>;
text_deque s_;
std::unique_ptr<node> odd, er;
int dn = 0;
node *back_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[n - cur->len - 1].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[n - suf->len - 1].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
node *front_appendable(const Char &ch, node *cur) {
int n = s_.size();
while (true) {
if (cur->len == -1 || (cur->len < n && s_[cur->len].ch == ch)) {
return cur;
}
node *suf = cur->lnk;
if (suf->len == -1 || s_[suf->len].ch == ch) {
return suf;
}
cur = cur->ql;
}
}
static node *transition(node *u, const Char &ch) {
auto it = u->nxt.find(ch);
assert(it != u->nxt.end());
return it->second;
}
public:
deque_palindromic_tree()
: odd(std::make_unique<node>()), er(std::make_unique<node>()) {
odd->len = -1;
odd->fa = odd->lnk = odd->ql = odd.get();
er->len = 0;
er->fa = er->lnk = er->ql = odd.get();
}
deque_palindromic_tree(const deque_palindromic_tree &) = delete;
deque_palindromic_tree &operator=(const deque_palindromic_tree &) = delete;
deque_palindromic_tree(deque_palindromic_tree &&) = delete;
deque_palindromic_tree &operator=(deque_palindromic_tree &&) = delete;
~deque_palindromic_tree() { clear(); }
int size() const { return s_.size(); }
bool empty() const { return s_.empty(); }
int distinct_palindromes() const { return dn; }
int longest_prefix_palindrome() const {
return empty() ? 0 : s_.front().ps->len;
}
int longest_suffix_palindrome() const {
return empty() ? 0 : s_.back().ss->len;
}
void push_back(const Char &ch) {
node *fa = empty() ? odd.get() : back_appendable(ch, s_.back().ss);
int n = size();
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = back_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_back({ch, er.get(), er.get()});
n++;
if (suf->lnk != odd.get() &&
s_[n - suf->len - 1].ch == s_[n - suf->lnk->len - 1].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_back({ch, er.get(), er.get()});
n++;
crt = old->second;
suf = crt->lnk;
}
s_[n - 1].ss = crt;
s_[n - crt->len].ps = crt;
if (suf->len >= 1 && s_[n - crt->len + suf->len - 1].ss == suf) {
s_[n - crt->len + suf->len - 1].ss = er.get();
}
crt->cnt++;
}
void push_front(const Char &ch) {
node *fa = empty() ? odd.get() : front_appendable(ch, s_.front().ps);
node *crt = nullptr;
node *suf = er.get();
auto old = fa->nxt.find(ch);
if (old == fa->nxt.end()) {
crt = new node();
crt->fa = fa;
crt->len = fa->len + 2;
if (fa != odd.get()) {
node *sp = front_appendable(ch, fa->lnk);
suf = transition(sp, ch);
}
crt->lnk = suf;
suf->il++;
s_.push_front({ch, er.get(), er.get()});
if (suf->lnk != odd.get() && s_[suf->len].ch == s_[suf->lnk->len].ch) {
crt->ql = suf->ql;
} else {
crt->ql = suf->lnk;
}
fa->nxt.emplace(ch, crt);
dn++;
} else {
s_.push_front({ch, er.get(), er.get()});
crt = old->second;
suf = crt->lnk;
}
s_[0].ps = crt;
s_[crt->len - 1].ss = crt;
if (suf->len >= 1 && s_[crt->len - suf->len].ps == suf) {
s_[crt->len - suf->len].ps = er.get();
}
crt->cnt++;
}
void pop_back() {
assert(!empty());
node *del = s_.back().ss;
Char ch = s_.back().ch;
node *suf = del->lnk;
int n = size();
if (del->len >= 2 && s_[n - del->len + suf->len - 1].ss->len < suf->len) {
s_[n - del->len + suf->len - 1].ss = suf;
s_[n - del->len].ps = suf;
} else {
s_[n - del->len].ps = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_back();
}
void pop_front() {
assert(!empty());
node *del = s_.front().ps;
Char ch = s_.front().ch;
node *suf = del->lnk;
if (del->len >= 2 && s_[del->len - suf->len].ps->len < suf->len) {
s_[del->len - suf->len].ps = suf;
s_[del->len - 1].ss = suf;
} else {
s_[del->len - 1].ss = er.get();
}
del->cnt--;
if (del->il == 0 && del->cnt == 0) {
std::size_t de1 = del->fa->nxt.erase(ch);
assert(de1 == 1);
suf->il--;
delete del;
dn--;
}
s_.pop_front();
}
void clear() {
while (!empty()) {
pop_back();
}
}
};
} // namespace noya