CompetitiveProgrammingCpp
This documentation is automatically generated by online-judge-tools/verification-helper
Test/String/LCPArray.test.cpp
- View this file on GitHub
- Last update: 2025-01-23 04:47:08+09:00
- Problem: https://yukicoder.me/problems/no/599
Depends on
- Library/Algebraic/Monoid.hpp
- Library/Algorithms/BinarySearch.hpp
- Library/DataStructure/SegmentTree.hpp
- Library/String/LCPArray.hpp
- Library/String/SuffixArray.hpp
Code
#define PROBLEM "https://yukicoder.me/problems/no/599"
#include "./../../Library/String/LCPArray.hpp"
#include <iostream>
#include "./../../Library/DataStructure/SegmentTree.hpp"
using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
Preprocessing() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
};
} _Preprocessing;
struct F {
auto operator()(int a, int b) const { return std::min(a, b); };
};
using M = mtd::Monoid<int, static_cast<int>(1e9), F>;
constexpr ll MOD = 1000000007;
signed main() {
std::string s;
cin >> s;
ll size = s.size();
auto lcparray = mtd::LCPArray(s);
auto segtree = mtd::SegmentTree<M>(size, lcparray.getLCPArray());
auto sai = lcparray.getSuffixArrayIndexList();
ll half = (size >> 1);
std::vector<ll> dp(half + 1);
dp[0] = 1;
for (int l = 0; l < half; ++l) {
for (int r = l; r < half; ++r) {
auto idx1 = sai[l];
auto idx2 = sai[size - r - 1];
if (idx2 < idx1) { std::swap(idx1, idx2); }
auto lcp = segtree.query(idx1, idx2 - 1);
int len = r - l + 1;
if (lcp >= len) {
dp[r + 1] += dp[l];
if (dp[r + 1] >= MOD) { dp[r + 1] -= MOD; }
}
}
}
ll ans = 0;
for (const auto& x : dp) {
ans += x;
if (ans >= MOD) { ans -= MOD; }
}
cout << ans;
}#line 1 "Test/String/LCPArray.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/599"
#line 2 "Library/String/LCPArray.hpp"
#line 2 "Library/String/SuffixArray.hpp"
#include <iostream>
#include <list>
#include <set>
#include <string>
#include <unordered_map>
#include <vector>
#line 2 "Library/Algorithms/BinarySearch.hpp"
#include <concepts>
#include <numeric>
#include <ranges>
#include <type_traits>
namespace mtd {
template <class Lambda>
auto binarySearch(double ok, double ng, int rep, const Lambda& is_ok) {
for ([[maybe_unused]] auto _ : std::views::iota(0, rep)) {
double mid = (ok + ng) / 2.0;
(is_ok(mid) ? ok : ng) = mid;
}
return ok;
}
template <class Lambda, std::integral T1, std::integral T2>
auto binarySearch(T1 ok_, T2 ng_, const Lambda& is_ok) {
using T = std::common_type_t<T1, T2>;
T ok = ok_, ng = ng_;
while (std::abs(ok - ng) > 1) {
T mid = (ok + ng) >> 1;
(is_ok(mid) ? ok : ng) = mid;
}
return ok;
}
} // namespace mtd
#line 10 "Library/String/SuffixArray.hpp"
namespace mtd {
/**
* SuffixArrayを構築する
* O(N)
* 文字列の全てのsuffixをソートした配列が得られる
* ex) abadc -> [0, 2, 1, 4, 3]([abadc, adc, badc, c, dc])
*
* SA-IS(Suffix Array - Induced Sort)で実装
*/
class SuffixArray {
enum class TYPE { L, S, LMS };
const std::string m_str;
const std::vector<int> m_suffixArray;
/* string to vector<int> */
static std::vector<int> toIntVec(const std::string& str) {
std::vector<int> vec;
vec.reserve(str.size() + 1);
for (const auto& c : str) { vec.emplace_back(c - '0' + 1); }
vec.emplace_back(0);
return vec;
}
/* classify { L, S, LMS } */
static std::vector<TYPE> classifying(const std::vector<int>& str) {
auto sz = static_cast<int>(str.size());
auto typeArray = std::vector<TYPE>(sz);
typeArray[sz - 1] = TYPE::S;
for (int i = sz - 2; i >= 0; --i) {
if (str[i] == str[i + 1]) {
typeArray[i] = typeArray[i + 1];
continue;
}
typeArray[i] = (str[i] < str[i + 1]) ? TYPE::S : TYPE::L;
}
for (int i = 1; i < sz; ++i) {
if (typeArray[i - 1] == TYPE::L && typeArray[i] == TYPE::S) {
typeArray[i] = TYPE::LMS;
}
}
return typeArray;
}
/* induced sort */
static std::vector<int> inducedSort(const std::vector<int>& str,
const std::vector<TYPE>& type,
std::list<int>& lmsList) {
auto sz = str.size();
auto nList = std::set<int>();
for (const auto& c : str) { nList.emplace(c); }
auto befCheck = [&](int k, auto& addList, bool rev) {
if (k == 0) { return; }
if (!rev && type[k - 1] == TYPE::L) {
addList[str[k - 1]].emplace_back(k - 1);
}
if (rev && type[k - 1] != TYPE::L) {
addList[str[k - 1]].emplace_front(k - 1);
}
};
auto checkAndUpdate = [&](int n, auto& checkList, auto& addList,
bool rev) {
auto& lst = checkList[n];
if (rev) {
for (auto itr = lst.rbegin(); itr != lst.rend(); ++itr) {
befCheck(*itr, addList, rev);
}
} else {
for (const auto& k : lst) { befCheck(k, addList, rev); }
}
};
/* set LMS */
auto tailList = std::unordered_map<int, std::list<int>>();
for (const auto& i : lmsList) { tailList[str[i]].emplace_back(i); }
/* set L-type */
auto headList = std::unordered_map<int, std::list<int>>();
for (const auto& n : nList) {
checkAndUpdate(n, headList, headList, false);
checkAndUpdate(n, tailList, headList, false);
}
/* set S-type*/
tailList = std::unordered_map<int, std::list<int>>();
for (auto itr_n = nList.rbegin(); itr_n != nList.rend(); ++itr_n) {
auto n = *itr_n;
checkAndUpdate(n, tailList, tailList, true);
checkAndUpdate(n, headList, tailList, true);
}
/* merge */
auto suffixArray = std::vector<int>();
suffixArray.reserve(sz);
for (const auto& n : nList) {
for (const auto& c : headList[n]) { suffixArray.emplace_back(c); }
for (const auto& c : tailList[n]) { suffixArray.emplace_back(c); }
}
return suffixArray;
}
/* order lms -> sorted lms */
static std::unordered_map<int, int> getLmsChanger(
const std::vector<int>& str, const std::vector<TYPE>& type,
const std::list<int>& lms) {
if (lms.size() == 1) {
return std::unordered_map<int, int>{{str.size() - 1, 0}};
}
std::unordered_map<int, int> changer{
{static_cast<int>(str.size()) - 1, 0}, {*++lms.begin(), 1}};
int num = 1;
for (auto itr = ++lms.begin(); itr != (--lms.end());) {
auto f1 = *itr;
auto f2 = *(++itr);
bool isSame = false;
for (int i = 0;; ++i) {
if (str[f1 + i] != str[f2 + i]) { break; }
auto b1 = (type[f1 + i] == TYPE::LMS);
auto b2 = (type[f2 + i] == TYPE::LMS);
if ((b1 || b2) && i > 0) {
if (b1 && b2) {
isSame = true;
break;
}
break;
}
}
if (!isSame) { ++num; }
changer.emplace(f2, num);
}
return changer;
}
/* calc Suffix Array*/
static std::vector<int> constructSuffixArray(const std::vector<int>& str) {
auto type = classifying(str);
/* calc fake Suffix Array using order seed*/
auto lmsOrder = [&type]() {
auto lms = std::list<int>();
for (size_t i = 0; i < type.size(); ++i)
if (type[i] == TYPE::LMS) { lms.emplace_back(i); }
return lms;
}();
auto fakeArray = inducedSort(str, type, lmsOrder);
/* calc true seed */
auto lmsFakeOrder = [&fakeArray, &type]() {
auto lms = std::list<int>();
lms.emplace_back(static_cast<int>(type.size()) - 1);
for (const auto& i : fakeArray)
if (type[i] == TYPE::LMS) { lms.emplace_back(i); }
return lms;
}();
auto changer = getLmsChanger(str, type, lmsFakeOrder);
auto& lmsTrueOrder = lmsFakeOrder;
if (changer[*lmsFakeOrder.rbegin()] + 1 <
static_cast<int>(lmsFakeOrder.size())) {
/* exist same lms-substring */
auto s = std::vector<int>();
auto def = std::vector<int>();
s.reserve(lmsOrder.size());
def.reserve(lmsOrder.size());
for (const auto& c : lmsOrder) {
s.emplace_back(changer[c]);
def.emplace_back(c);
}
auto lmsSuffixArray = constructSuffixArray(s);
lmsTrueOrder = std::list<int>{static_cast<int>(type.size()) - 1};
for (const auto& c : lmsSuffixArray) {
lmsTrueOrder.emplace_back(def[c]);
}
}
/* calc true Suffix Array using true seed */
auto suffixArray = inducedSort(str, type, lmsTrueOrder);
return suffixArray;
}
public:
SuffixArray(const std::string& str)
: m_str(str), m_suffixArray(constructSuffixArray(toIntVec(str))) {}
/**
* 引数として与えられたpattern出現位置の区間を返す
*/
std::pair<int, int> findPattern(const std::string& pattern) const {
auto find = [&](const std::string& ptn) {
int end = static_cast<int>(m_suffixArray.size());
int ptn_sz = static_cast<int>(ptn.size());
auto ret = binarySearch(end, -1, [&](int mid) {
int st = m_suffixArray[mid];
int sub_sz = end - st;
for (int k = 0; k < std::min(ptn_sz, sub_sz); ++k) {
if (ptn[k] < m_str[st + k]) { return true; }
if (ptn[k] > m_str[st + k]) { return false; }
}
return ptn_sz <= sub_sz;
});
return ret;
};
auto patternUpper = [&pattern]() {
auto ptn = pattern;
++*ptn.rbegin();
return ptn;
}();
auto fl = find(pattern);
auto fu = find(patternUpper);
return {fl, fu};
}
auto getSuffixArray() const { return m_suffixArray; }
/* output fot debug */
void debugOutput() const {
for (const auto& x : m_suffixArray) { std::cout << x << " "; }
std::cout << std::endl;
auto end = m_str.size();
for (const auto& x : m_suffixArray) {
std::cout << m_str.substr(x, end) << std::endl;
}
}
};
} // namespace mtd
#line 4 "Library/String/LCPArray.hpp"
namespace mtd {
/**
* LCPArrayを構築する
* O(N)
* suffix arrayで隣接するstrの最長共通接頭辞(LCP:Longest Common Prefix)を得る
* ex) sa:[aab, ab, abaab, b, baab] -> LCPA:[1, 2, 0, 1]
*
* Kasai's algorithmで実装
*/
class LCPArray {
const std::vector<int> m_suffixArray;
const std::vector<int> m_lcpArray;
static std::vector<int> constructLcpArray(const std::string& str) {
auto sz = static_cast<int>(str.size());
const auto suffixArray = SuffixArray(str).getSuffixArray();
auto rank = std::vector<int>(sz);
for (int i = 0; i < sz; ++i) { rank[suffixArray[i]] = i; }
auto lcpArray = std::vector<int>(sz - 1);
for (int i = 0, h = 0; i < sz; ++i) {
if (rank[i] == 0) { continue; }
int j = suffixArray[rank[i] - 1];
if (h > 0) { --h; }
for (; j + h < sz && i + h < sz; ++h) {
if (str[i + h] != str[j + h]) { break; }
}
lcpArray[rank[i] - 1] = h;
}
return lcpArray;
}
public:
LCPArray(const std::string& str)
: m_suffixArray(SuffixArray(str).getSuffixArray()),
m_lcpArray(constructLcpArray(str)) {}
auto getLCPArray() const { return m_lcpArray; }
auto getSuffixArrayIndexList() const {
std::vector<int> sail(m_suffixArray.size());
for (unsigned int i = 0; i < m_suffixArray.size(); ++i) {
sail[m_suffixArray[i]] = i;
}
return sail;
}
};
} // namespace mtd
#line 4 "Test/String/LCPArray.test.cpp"
#line 6 "Test/String/LCPArray.test.cpp"
#line 2 "Library/DataStructure/SegmentTree.hpp"
#include <deque>
#line 5 "Library/DataStructure/SegmentTree.hpp"
#include <utility>
#line 7 "Library/DataStructure/SegmentTree.hpp"
#line 2 "Library/Algebraic/Monoid.hpp"
#line 4 "Library/Algebraic/Monoid.hpp"
namespace mtd {
template <class S, // set
S element, // identity element
class op // binary operation
>
requires std::is_invocable_r_v<S, op, S, S>
struct Monoid {
using value_type = S;
constexpr static S _element = element;
using op_type = op;
S m_val;
constexpr Monoid(S val) : m_val(val) {}
constexpr Monoid() : Monoid(element) {}
constexpr Monoid binaryOperation(const Monoid& m2) const {
return op()(m_val, m2.m_val);
}
friend std::ostream& operator<<(std::ostream& os,
const Monoid<S, element, op>& m) {
return os << m.m_val;
}
};
namespace __detail {
template <typename T, template <typename, auto, typename> typename S>
concept is_monoid_specialization_of = requires {
typename std::enable_if_t<std::is_same_v<
T, S<typename T::value_type, T::_element, typename T::op_type>>>;
};
} // namespace __detail
template <typename M>
concept monoid = __detail::is_monoid_specialization_of<M, Monoid>;
} // namespace mtd
#line 9 "Library/DataStructure/SegmentTree.hpp"
namespace mtd {
template <monoid Monoid>
class SegmentTree {
private:
const int m_size;
std::vector<Monoid> m_node;
using S = decltype(Monoid().m_val);
constexpr int calcSize(int n) const {
int size = 1;
while (size < n) { size <<= 1; }
return size;
}
template <class Lambda>
constexpr auto _update_op(int itr, Monoid&& val, const Lambda& op) {
int i = itr + m_size - 1;
m_node[i] = op(m_node[i], std::forward<decltype(val)>(val));
while (i) {
i = (i - 1) >> 1;
m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
}
}
constexpr auto _query(int _l, int _r) const {
auto l = std::max(_l, 0) + m_size;
auto r = std::min(_r, m_size - 1) + m_size;
auto lm = Monoid();
auto rm = Monoid();
while (l <= r) {
if (l & 1) {
lm = lm.binaryOperation(m_node[l - 1]);
++l;
}
if (!(r & 1)) {
rm = m_node[r - 1].binaryOperation(rm);
--r;
}
l >>= 1, r >>= 1;
}
return lm.binaryOperation(rm);
}
constexpr auto _construct(const std::vector<S>& vec) {
for (unsigned int i = 0; i < vec.size(); ++i) {
m_node[i + m_size - 1] = Monoid(vec[i]);
}
for (int i = m_size - 2; i >= 0; --i) {
m_node[i] = m_node[(i << 1) | 1].binaryOperation(m_node[(i + 1) << 1]);
}
}
public:
SegmentTree(int n) : m_size(calcSize(n)), m_node((m_size << 1) - 1) {}
SegmentTree(int n, const std::vector<S>& vec) : SegmentTree(n) {
_construct(vec);
}
template <class Lambda>
constexpr auto update_op(int itr, Monoid&& val, const Lambda& op) {
return _update_op(itr, std::forward<Monoid>(val), op);
}
constexpr auto update(int itr, Monoid&& val) {
return update_op(itr, std::forward<Monoid>(val),
[](const Monoid&, const Monoid& m2) { return m2; });
}
constexpr auto add(int itr, Monoid&& val) {
return update_op(itr, std::forward<Monoid>(val),
[](const Monoid& m1, const Monoid& m2) {
return Monoid(m1.m_val + m2.m_val);
});
}
constexpr auto query(int l, int r) const { return _query(l, r).m_val; }
constexpr auto query_all() const { return m_node[0].m_val; }
/*
* f([l, r]) = true となる最大のr
* judge: (Monoid) -> bool
**/
template <class F>
constexpr auto max_right(int _l, const F& judge) const {
if (!judge(Monoid())) {
throw std::runtime_error("SegmentTree.max_right.judge(e) must be true");
}
auto l = std::max(_l, 0) + m_size;
auto r = 2 * m_size - 1;
auto lm = Monoid();
while (l <= r) {
if (l & 1) {
auto next = lm.binaryOperation(m_node[l - 1]);
if (!judge(next)) {
auto itr = l;
while (itr < m_size) {
auto litr = 2 * itr;
auto ritr = 2 * itr + 1;
auto lval = lm.binaryOperation(m_node[litr - 1]);
if (!judge(lval)) {
itr = litr;
} else {
itr = ritr;
std::swap(lm, lval);
}
}
return itr - m_size - 1;
}
std::swap(lm, next);
++l;
}
l >>= 1, r >>= 1;
}
return m_size - 1;
}
/*
* f([l, r]) = true となる最小のl
* judge: (Monoid) -> bool
**/
template <class F>
constexpr auto min_left(int _r, const F& judge) const {
if (!judge(Monoid())) {
throw std::runtime_error("SegmentTree.min_left.judge(e) must be true");
}
auto l = m_size;
auto r = std::min(_r, m_size - 1) + m_size;
auto rm = Monoid();
while (l <= r) {
if (l & 1) { ++l; }
if (!(r & 1) || (_r == m_size - 1 && r == 1)) {
auto next = m_node[r - 1].binaryOperation(rm);
if (!judge(next)) {
auto itr = r;
while (itr < m_size) {
auto litr = 2 * itr;
auto ritr = 2 * itr + 1;
auto rval = m_node[ritr - 1].binaryOperation(rm);
if (!judge(rval)) {
itr = ritr;
} else {
itr = litr;
std::swap(rm, rval);
}
}
return itr - m_size + 1;
}
std::swap(rm, next);
--r;
}
l >>= 1, r >>= 1;
}
return 0;
}
constexpr auto debug() const {
for (int i = 0; i < m_size; ++i) {
std::cout << m_node[m_size + i - 1] << " ";
}
std::cout << std::endl;
}
};
} // namespace mtd
#line 8 "Test/String/LCPArray.test.cpp"
using ll = long long;
using std::cin;
using std::cout;
constexpr char endl = '\n';
struct Preprocessing {
Preprocessing() {
std::cin.tie(0);
std::ios::sync_with_stdio(0);
};
} _Preprocessing;
struct F {
auto operator()(int a, int b) const { return std::min(a, b); };
};
using M = mtd::Monoid<int, static_cast<int>(1e9), F>;
constexpr ll MOD = 1000000007;
signed main() {
std::string s;
cin >> s;
ll size = s.size();
auto lcparray = mtd::LCPArray(s);
auto segtree = mtd::SegmentTree<M>(size, lcparray.getLCPArray());
auto sai = lcparray.getSuffixArrayIndexList();
ll half = (size >> 1);
std::vector<ll> dp(half + 1);
dp[0] = 1;
for (int l = 0; l < half; ++l) {
for (int r = l; r < half; ++r) {
auto idx1 = sai[l];
auto idx2 = sai[size - r - 1];
if (idx2 < idx1) { std::swap(idx1, idx2); }
auto lcp = segtree.query(idx1, idx2 - 1);
int len = r - l + 1;
if (lcp >= len) {
dp[r + 1] += dp[l];
if (dp[r + 1] >= MOD) { dp[r + 1] -= MOD; }
}
}
}
ll ans = 0;
for (const auto& x : dp) {
ans += x;
if (ans >= MOD) { ans -= MOD; }
}
cout << ans;
}