fork download
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define sz(a) (int)(a).size()
  5. #define all(a) (a).begin(), (a).end()
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. #include <bits/stdc++.h>
  10.  
  11. using namespace __gnu_pbds;
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef pair<int, int> pii;
  17.  
  18. typedef
  19. tree<
  20. pii,
  21. null_type,
  22. less<pii>,
  23. rb_tree_tag,
  24. tree_order_statistics_node_update>
  25. ordered_set;
  26.  
  27. const int nmax = 1e6 + 100;
  28. const int inf = 1e9;
  29. const int rmax = 22;
  30.  
  31. int sparse[rmax][nmax];
  32. int deg[nmax];
  33.  
  34. int p[nmax], pos[nmax], lcp[nmax];
  35. int cnt[nmax];
  36. int c[nmax];
  37. int cn[nmax], pn[nmax];
  38.  
  39. void suffixArray(const string& s) {
  40. int n = sz(s);
  41. for (int i = 0; i < n; ++i) {
  42. ++cnt[s[i]];
  43. }
  44. for (int i = 1; i < nmax; ++i) {
  45. cnt[i] += cnt[i - 1];
  46. }
  47. for (int i = n - 1; i >= 0; --i) {
  48. p[--cnt[s[i]]] = i;
  49. }
  50. c[p[0]] = 0;
  51. for (int i = 1; i < n; ++i) {
  52. c[p[i]] = c[p[i - 1]];
  53. if (s[p[i]] != s[p[i - 1]]) {
  54. ++c[p[i]];
  55. }
  56. }
  57. int len = 1;
  58. for (int j = 0; len < n; ++j, len <<= 1) {
  59. for (int i = 0; i < n; ++i) {
  60. pn[i] = p[i] - len;
  61. if (pn[i] < 0) {
  62. pn[i] += n;
  63. }
  64. }
  65. memset(cnt, 0, sizeof(cnt));
  66. for (int i = 0; i < n; ++i) {
  67. ++cnt[c[i]];
  68. }
  69. for (int i = 1; i < n; ++i) {
  70. cnt[i] += cnt[i - 1];
  71. }
  72. for (int i = n - 1; i >= 0; --i) {
  73. p[--cnt[c[pn[i]]]] = pn[i];
  74. }
  75. cn[p[0]] = 0;
  76. for (int i = 1; i < n; ++i) {
  77. cn[p[i]] = cn[p[i - 1]];
  78. if (c[p[i]] != c[p[i - 1]]) {
  79. ++cn[p[i]];
  80. continue;
  81. }
  82. int x = p[i] + len;
  83. if (x >= n) {
  84. x -= n;
  85. }
  86. int y = p[i - 1] + len;
  87. if (y >= n) {
  88. y -= n;
  89. }
  90. if (c[x] != c[y]) {
  91. ++cn[p[i]];
  92. }
  93. }
  94. memcpy(c, cn, sizeof(c));
  95. }
  96. for (int i = 0; i < n; ++i) {
  97. pos[p[i]] = i;
  98. }
  99. int k = 0;
  100. for (int i = 0; i < n; ++i) {
  101. if (pos[i] == n - 1) {
  102. k = 0;
  103. continue;
  104. }
  105. k = max(k - 1, 0);
  106. int j = p[pos[i] + 1];
  107. while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
  108. ++k;
  109. }
  110. lcp[pos[i]] = k;
  111. }
  112. }
  113.  
  114. struct query {
  115. ll k;
  116. int id;
  117. bool operator<(const query& other) const {
  118. return k < other.k;
  119. }
  120. };
  121.  
  122. void rem(ordered_set& s, int x) {
  123. pii pp = {x, inf};
  124. ordered_set::iterator it = s.upper_bound(pp);
  125. --it;
  126. int l = it->first, r = it->second;
  127. assert(l <= x && x <= r);
  128. s.erase(it);
  129. if (l <= x - 1) {
  130. s.insert({l, x - 1});
  131. }
  132. if (x + 1 <= r) {
  133. s.insert({x + 1, r});
  134. }
  135. }
  136.  
  137. void split(ordered_set& s, int z) {
  138. pii pp = {z, inf};
  139. ordered_set::iterator it = s.upper_bound(pp);
  140. //cout << "!" << it->first << " " << it->second << endl;
  141. --it;
  142. int l = it->first, r = it->second;
  143.  
  144. assert(l <= z && z + 1 <= r);
  145. s.erase(it);
  146. s.insert({l, z});
  147. s.insert({z + 1, r});
  148. }
  149.  
  150. int getMax(int l, int r) {
  151. int k = deg[r - l + 1];
  152. return max(sparse[k][l], sparse[k][r - (1 << k) + 1]);
  153. }
  154.  
  155. int main() {
  156.  
  157. ios_base::sync_with_stdio(false);
  158. cin.tie(0);
  159. cout.tie(0);
  160.  
  161. //ifstream cin("input.txt");
  162.  
  163. deg[0] = -1;
  164. for (int i = 1; i < nmax; ++i) {
  165. deg[i] = deg[i - 1];
  166. if (!(i & (i - 1))) {
  167. ++deg[i];
  168. }
  169. }
  170.  
  171. string s;
  172. cin >> s;
  173. s += "#";
  174. int n = sz(s);
  175.  
  176. suffixArray(s);
  177.  
  178. int q;
  179. cin >> q;
  180. vector<query> queries(q);
  181. for (int i = 0; i < q; ++i) {
  182. cin >> queries[i].k;
  183. queries[i].id = i;
  184. }
  185. sort(all(queries));
  186.  
  187. ordered_set setik;
  188. int l = 1;
  189. for (int r = 2; r < n; ++r) {
  190. if (s[p[r]] != s[p[l]]) {
  191. setik.insert({l, r - 1});
  192. l = r;
  193. }
  194. }
  195. setik.insert({l, n - 1});
  196. int curLen = 1;
  197.  
  198. ll skipped = 0;
  199. vector<pii> ans(q, {-1, -1});
  200.  
  201. vector<vector<int> > equalLCP(n + 1);
  202. for (int i = 0; i < n - 1; ++i) {
  203. equalLCP[lcp[i]].pb(i);
  204. }
  205.  
  206. /*for (int i = 0; i < n - 1; ++i) {
  207.   cout << lcp[i] << "\n";
  208.   }
  209.   return 0;*/
  210.  
  211. /*for (pii pp : setik) {
  212.   cout << pp.first << " " << pp.second << endl;
  213.   }
  214.  
  215.   return 0;*/
  216.  
  217. for (int i = 0; i < n; ++i) {
  218. sparse[0][i] = n - p[i];
  219. }
  220. for (int r = 0; r + 1 < rmax; ++r) {
  221. for (int i = 0; i < n; ++i) {
  222. int j = min(n - 1, i + (1 << r));
  223. sparse[r + 1][i] = max(sparse[r][i], sparse[r][j]);
  224. }
  225. }
  226.  
  227. for (query Q : queries) {
  228. Q.k -= skipped;
  229. bool bad = false;
  230. while (Q.k > sz(setik)) {
  231. if (curLen == n) {
  232. bad = true;
  233. break;
  234. }
  235. skipped += sz(setik);
  236. Q.k -= sz(setik);
  237. int x = pos[n - curLen - 1];
  238. rem(setik, x);
  239. for (int z : equalLCP[curLen]) {
  240. //cout << "!" << z << endl;
  241. int len = n - p[z] - 1;
  242. if (len <= curLen) {
  243. continue;
  244. }
  245. len = n - p[z + 1] - 1;
  246. if (len <= curLen) {
  247. continue;
  248. }
  249. split(setik, z);
  250. }
  251. ++curLen;
  252. }
  253.  
  254. if (bad) {
  255. continue;
  256. }
  257. // pp - kth pair in setik
  258. pii pp = *(setik.find_by_order(Q.k - 1));
  259. int l = pp.first, r = pp.second;
  260. //cout << "!" << pp.first << " " << pp.second << endl;
  261. int len = getMax(l, r);
  262. ans[Q.id] = {n - len + 1, n - len + 1 + curLen - 1};
  263. //cout << Q.id << " " << curLen << endl;
  264. //cout << "!" << skipped << endl;
  265. }
  266.  
  267. for (int i = 0; i < q; ++i) {
  268. cout << ans[i].first << " " << ans[i].second << "\n";
  269. }
  270.  
  271. }
  272.  
Runtime error #stdin #stdout #stderr 0.01s 23984KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc