#include #ifdef DEBUG #include #else #define dump(...) #endif /** * @title Suffix array * @docs suffix_array.md */ template struct SuffixArray { Container s; int N; std::vector data; SuffixArray(Container s): s(s), N(s.size()), data(N){ if(N == 1){ data = {1, 0}; return; } s.resize(N + 1); std::string LS(N + 1, 'S'); for(int i = N; --i >= 0;){ if(s[i] < s[i + 1]) LS[i] = 'S'; else if(s[i] > s[i + 1]) LS[i] = 'L'; else LS[i] = LS[i + 1]; } const int bucket_count = *std::max_element(s.begin(), s.end()); std::vector bucket_size(bucket_count + 1); for(auto x : s) bucket_size[x] += 1; auto induced_sort = [&](std::vector LMS){ std::vector bucket(N + 1, -1); std::vector is_lms(N + 1); std::vector> empty(bucket_count + 1); for(int i = 0, k = 0; i <= bucket_count; ++i){ for(int j = 0; j < bucket_size[i]; ++j){ empty[i].push_back(k); ++k; } } std::reverse(LMS.begin(), LMS.end()); for(auto x : LMS){ int i = empty[s[x]].back(); empty[s[x]].pop_back(); bucket[i] = x; is_lms[i] = true; } for(int i = 0; i <= N; ++i){ if(bucket[i] >= 1 and LS[bucket[i] - 1] == 'L'){ auto x = s[bucket[i] - 1]; int j = empty[x].front(); empty[x].pop_front(); bucket[j] = bucket[i] - 1; } } for(int i = 0; i <= N; ++i){ if(is_lms[i]){ bucket[i] = -1; } } for(int i = 0, k = 0; i <= bucket_count; ++i){ empty[i].clear(); for(int j = 0; j < bucket_size[i]; ++j){ empty[i].push_back(k); ++k; } } for(int i = N; i >= 0; --i){ if(bucket[i] >= 1 and LS[bucket[i] - 1] == 'S'){ auto x = s[bucket[i] - 1]; int j = empty[x].back(); empty[x].pop_back(); bucket[j] = bucket[i] - 1; } } bucket[0] = N; return bucket; }; std::vector LMS; for(int i = 1; i <= N; ++i){ if(LS[i] == 'S' and LS[i - 1] == 'L'){ LMS.push_back(i); } } std::vector LMS_bucket_length(N + 1, 1); for(int i = 0; i < (int)LMS.size() - 1; ++i){ LMS_bucket_length[LMS[i]] = LMS[i + 1] - LMS[i] + 1; } auto bucket = induced_sort(LMS); std::vector LMS_substr_sorted; for(int i : bucket){ if(i > 0 and LS[i - 1] == 'L' and LS[i] == 'S'){ LMS_substr_sorted.push_back(i); } } std::vector rank(N + 1); rank[LMS_substr_sorted[0]] = 1; for(int i = 1, k = 1; i < (int)LMS_substr_sorted.size(); ++i){ const int x = LMS_substr_sorted[i - 1], y = LMS_substr_sorted[i]; bool eq = true; if(LMS_bucket_length[x] != LMS_bucket_length[y]) eq = false; else{ for(int j = 0; j < LMS_bucket_length[x]; ++j){ if(s[x + j] != s[y + j]) eq = false; } } if(not eq) ++k; rank[y] = k; } std::vector t; for(int i = 0; i <= N; ++i){ if(rank[i] != 0) t.push_back(rank[i]); } auto sa = SuffixArray>(t).data; std::vector LMS_sorted; for(int i = 1; i < (int)sa.size(); ++i){ LMS_sorted.push_back(LMS[sa[i]]); } data = induced_sort(LMS_sorted); } int operator[](size_t i) const {return data[i];} auto begin() const {return data.begin();} auto end() const {return data.end();} size_t size() const {return data.size();} }; /** * @title LCP(Longest Common Prefix) array * @docs lcp_array.md */ template struct LCPArray { int n; std::vector data, rank; LCPArray(const SuffixArray &sa): n(sa.size()), data(n), rank(n){ for(int i = 0; i < n; ++i) rank[sa[i]] = i; int h = 0; for(int i = 0; i < n; ++i){ if(rank[i] == 0) continue; int j = sa[rank[i] - 1]; if(h) --h; while(j + h < n and i + h < n){ if(sa.s[j + h] != sa.s[i + h]) break; ++h; } data[rank[i]] = h; } } int operator[](size_t i) const {return data[i];} auto begin() const {return data.begin();} auto end() const {return data.end();} }; /** * @title Sparse table * @docs sparse_table.md */ template class SparseTable { using value_type = typename Semilattice::value_type; const static Semilattice S; std::vector> a; std::vector log_table; public: template SparseTable(const std::vector &v){ int n = v.size(); int logn = 0; while((1 << logn) <= n) ++logn; a.assign(n, std::vector(logn)); for(int i = 0; i < n; ++i) a[i][0] = v[i]; for(int j = 1; j < logn; ++j){ for(int i = 0; i < n; ++i){ a[i][j] = S(a[i][j - 1], a[std::min(n - 1, i + (1 << (j - 1)))][j - 1]); } } log_table.assign(n + 1, 0); for(int i = 2; i < n + 1; ++i) log_table[i] = log_table[i >> 1] + 1; } value_type get(int s, int t) const { // [s,t) int k = log_table[t - s]; return S(a[s][k], a[t - (1 << k)][k]); } value_type get(std::vector> st) const { value_type ret; bool t = true; for(const auto &p : st){ if(p.first < p.second){ if(t){ ret = get(p.first, p.second); t = false; }else{ ret = S(ret, get(p.first, p.second)); } } } return ret; } }; /** * @title Min monoid * @docs min.md */ template struct MinMonoid { using value_type = std::optional; value_type operator()() const {return {};} value_type operator()(const value_type &a, const value_type &b) const { if(not a) return b; if(not b) return a; return {std::min(*a, *b)}; } }; void query(int N, int M, int64_t x, int64_t d, std::function f){ for(int k = 0; k < M; ++k){ int i = x / (N - 1); int j = x % (N - 1); if(i > j) std::swap(i, j); else j += 1; x = (x + d) % (N * (N - 1)); f(i, j); } } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); int N; std::cin >> N; std::vector s(N); for(int i = 0; i < N; ++i) std::cin >> s[i]; int M; std::cin >> M; int64_t x, d; std::cin >> x >> d; std::stringstream ss; std::vector pos(N); for(int i = 0, p = 0; i < N; ++i){ pos[i] = p; ss << s[i] << "$"; p += s[i].size() + 1; } std::string S = ss.str(); auto sa = SuffixArray(S); auto lcp = LCPArray(sa); auto rmq = SparseTable>(lcp.data); int64_t ans = 0; query(N, M, x, d, [&](int i, int j){ int a = lcp.rank[pos[i]]; int b = lcp.rank[pos[j]]; if(a > b) std::swap(a, b); auto res = rmq.get(a + 1, b + 1); ans += std::min({*res, (int)s[i].size(), (int)s[j].size()}); } ); std::cout << ans << "\n"; return 0; }