#line 1 "main.cpp" #include #include #include #include #include #line 4 "/home/kokoro601/compro_library/String/SuffixArray.hpp" #include #line 6 "/home/kokoro601/compro_library/String/SuffixArray.hpp" #include #line 3 "/home/kokoro601/compro_library/DataStructure/SparseTable.hpp" template class SparseTable { public: std::vector > tab; std::vector lookup; void build(const std::vector &v) { int b = 0; int n = v.size(); while (1 << b <= n) b++; tab.assign(b, std::vector(1 << b)); for (int i = 0; i < n; i++) tab[0][i] = v[i]; for (int i = 1; i < b; i++) { int pre_len = 1 << (i - 1); int ub = n - (1 << i); for (int j = 0; j <= ub; j++) { tab[i][j] = std::min(tab[i - 1][j], tab[i - 1][j + pre_len]); } } lookup.resize(v.size() + 1); for (int i = 2; i < lookup.size(); i++) lookup[i] = lookup[i >> 1] + 1; } // [l, r) inline T rmq(int l, int r) { // assert(l < r); int b = lookup[r - l]; return std::min(tab[b][l], tab[b][r - (1 << b)]); } }; #line 8 "/home/kokoro601/compro_library/String/SuffixArray.hpp" // this implemantation is based on // https://megalodon.jp/2022-0430-1612-24/https://wk1080id.hatenablog.com:443/entry/2018/12/25/005926 // the construction of suffix array is O(nlogn), where n is the length of the string class SuffixArray { std::vector sort_cyclic_shifts(const std::string &s) { int n = s.size(); std::vector cn(n), pn(n), p(n), c(n), cnt(n); std::iota(p.begin(), p.end(), 0); std::sort(p.begin(), p.end(), [&](int a, int b) { return s[a] == s[b] ? a < b : s[a] < s[b]; }); c[p[0]] = 0; for (int i = 1; i < n; i++) c[p[i]] = (s[p[i]] == s[p[i - 1]]) ? c[p[i - 1]] : i; for (int len = 1; len < n; len <<= 1) { for (int i = 0; i < n; i++) { pn[i] = p[i] - len; if (pn[i] < 0) pn[i] += n; } std::iota(cnt.begin(), cnt.end(), 0); for (int i = 0; i < n; i++) p[cnt[c[pn[i]]]++] = pn[i]; if (2 * len >= n) break; c[p[0]] = 0; for (int i = 1; i < n; i++) { if (c[p[i]] == c[p[i - 1]] && c[(p[i] + len) % n] == c[(p[i - 1] + len) % n]) cn[p[i]] = cn[p[i - 1]]; else cn[p[i]] = i; } std::swap(c, cn); } return p; } void calc_lcp(std::string &s) { int n = sa.size(); int slen = n - 1; rank.resize(n); lcp.resize(n); for (int i = 0; i < n; i++) rank[sa[i]] = i; int h = 0; lcp[0] = 0; for (int i = 0; i < slen; i++) { int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < n && i + h < n; h++) if (s[j + h] != s[i + h]) break; lcp[rank[i] - 1] = h; } st.build(lcp); } public: std::vector sa, lcp, rank; SparseTable st; bool need_lcp; SuffixArray(std::string &s, bool need_lcp = true): need_lcp(need_lcp) { s.push_back('$'); sa = sort_cyclic_shifts(s); s.pop_back(); if (need_lcp) calc_lcp(s); } int get_lcp(int i, int j) { assert(need_lcp && i != j); int rank_i = rank[i]; int rank_j = rank[j]; if (rank_i > rank_j) std::swap(rank_i, rank_j); return st.rmq(rank_i, rank_j); } }; #line 7 "main.cpp" using namespace std; using ll = long long; using Graph = vector >; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; vector l(n), offset(n + 1); string s = ""; for (int i = 0; i < n; i++) { string si; cin >> si; l[i] = si.size(); offset[i + 1] = offset[i] + l[i]; s += si; } SuffixArray sa(s); int m; ll x, d; cin >> m >> x >> d; ll ans = 0; for (int k = 0; k < m; k++) { ll i = (x / (n - 1)) + 1; ll j = (x % (n - 1)) + 1; if (i > j) swap(i, j); else j = j + 1; ans += min(min(l[i - 1], l[j - 1]), sa.get_lcp(offset[i - 1], offset[j - 1])); x = (x + d) % (n * (n - 1)); } cout << ans << endl; return 0; }