#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; const int inf=1<<30; const ll INF=1LL<<62; typedef pair P; typedef pair PP; const ll MOD=998244353; // SA-IS (O(N)) template struct SuffixArray { // data Str str; //sa[0]は空文字になっていることに注意 vector sa, rsa, lcp;//勝手に代入される int& operator [] (int i) { return sa[i]; } // constructor SuffixArray(const Str& str_) : str(str_) { build_sa(); } void init(const Str& str_) { str = str_; build_sa(); } void build_sa() { int N = (int)str.size(); vector s; for (int i = 0; i < N; ++i) s.push_back(str[i] + 1); s.push_back(0); sa = sa_is(s); rsa.assign(N + 1, 0); for (int i = 0; i <= N; ++i) rsa[sa[i]] = i; calc_lcp(s); } // SA-IS // upper: # of characters vector sa_is(vector &s, int upper = 256) { int N = (int)s.size(); if (N == 0) return {}; else if (N == 1) return {0}; else if (N == 2) { if (s[0] < s[1]) return {0, 1}; else return {1, 0}; } vector isa(N); vector ls(N, false); for (int i = N - 2; i >= 0; --i) { ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]); } vector sum_l(upper + 1, 0), sum_s(upper + 1, 0); for (int i = 0; i < N; ++i) { if (!ls[i]) ++sum_s[s[i]]; else ++sum_l[s[i] + 1]; } for (int i = 0; i <= upper; ++i) { sum_s[i] += sum_l[i]; if (i < upper) sum_l[i + 1] += sum_s[i]; } auto induce = [&](const vector &lms) -> void { fill(isa.begin(), isa.end(), -1); vector buf(upper + 1); copy(sum_s.begin(), sum_s.end(), buf.begin()); for (auto d: lms) { if (d == N) continue; isa[buf[s[d]]++] = d; } copy(sum_l.begin(), sum_l.end(), buf.begin()); isa[buf[s[N - 1]]++] = N - 1; for (int i = 0; i < N; ++i) { int v = isa[i]; if (v >= 1 && !ls[v - 1]) { isa[buf[s[v - 1]]++] = v - 1; } } copy(sum_l.begin(), sum_l.end(), buf.begin()); for (int i = N - 1; i >= 0; --i) { int v = isa[i]; if (v >= 1 && ls[v - 1]) { isa[--buf[s[v - 1] + 1]] = v - 1; } } }; vector lms, lms_map(N + 1, -1); int M = 0; for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms_map[i] = M++; } } lms.reserve(M); for (int i = 1; i < N; ++i) { if (!ls[i - 1] && ls[i]) { lms.push_back(i); } } induce(lms); if (M) { vector lms2; lms2.reserve(isa.size()); for (auto v: isa) { if (lms_map[v] != -1) lms2.push_back(v); } int rec_upper = 0; vector rec_s(M); rec_s[lms_map[lms2[0]]] = 0; for (int i = 1; i < M; ++i) { int l = lms2[i - 1], r = lms2[i]; int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N; int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N; bool same = true; if (nl - l != nr - r) same = false; else { while (l < nl) { if (s[l] != s[r]) break; ++l, ++r; } if (l == N || s[l] != s[r]) same = false; } if (!same) ++rec_upper; rec_s[lms_map[lms2[i]]] = rec_upper; } auto rec_sa = sa_is(rec_s, rec_upper); vector sorted_lms(M); for (int i = 0; i < M; ++i) { sorted_lms[i] = lms[rec_sa[i]]; } induce(sorted_lms); } return isa; } // prepair lcp vector calc_lcp(const vector &s) { int N = (int)s.size(); lcp.assign(N - 1, 0); int h = 0; for (int i = 0; i < N - 1; ++i) { int pi = sa[rsa[i] - 1]; if (h > 0) --h; for (; pi + h < N && i + h < N; ++h) { if (s[pi + h] != s[i + h]) break; } lcp[rsa[i] - 1] = h; } return lcp; } }; struct z_algorithm{ std::string s; int len; std::vector z_array; bool is_build; z_algorithm(const std::string& s_):s(s_),len(s_.size()),is_build(false){ z_array=std::vector(len); build(); } ~z_algorithm(){ std::vector().swap(z_array); } void build(){ is_build = true; z_array[0]=len; int i=1; int j=0; while(i0 int k=1; while(k