fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. #define endl "\n"
  5.  
  6. ll clz(ll N)
  7. {
  8. ll idx{};
  9. for (int i = 0; i < 32; i++)
  10. {
  11. if (N & (1LL << i))
  12. idx = i;
  13. }
  14. return 31 - idx;
  15. }
  16.  
  17. namespace SuffixArray
  18. {
  19. const int maxN = 4e5 + 10;
  20. string S;
  21. ll N, gap;
  22. int SA[maxN], pos[maxN], tmp[maxN];
  23. vector<int> lcp(maxN);
  24. vector<vector<int>> m;
  25.  
  26. bool sufCmp(int i, int j)
  27. {
  28. if (pos[i] != pos[j])
  29. return pos[i] < pos[j];
  30. i += gap;
  31. j += gap;
  32. return (i < N && j < N) ? pos[i] < pos[j] : i > j;
  33. }
  34.  
  35. void buildSA()
  36. {
  37. N = S.size();
  38. for (int i{}; i < N; i++)
  39. SA[i] = i,
  40. pos[i] = S[i];
  41. for (gap = 1;; gap *= 2)
  42. {
  43. sort(SA, SA + N, sufCmp);
  44. for (int i{}; i < N - 1; i++)
  45. tmp[i + 1] = tmp[i] + sufCmp(SA[i], SA[i + 1]);
  46. for (int i{}; i < N; i++)
  47. pos[SA[i]] = tmp[i];
  48. if (tmp[N - 1] == N - 1)
  49. break;
  50. }
  51. }
  52.  
  53. void buildLCP()
  54. {
  55. for (int i = 0, k = 0; i < N; ++i)
  56. {
  57. if (pos[i] != N - 1)
  58. {
  59. for (int j = SA[pos[i] + 1]; S[i + k] == S[j + k];)
  60. ++k;
  61. lcp[pos[i]] = k;
  62. if (k)
  63. --k;
  64. }
  65. }
  66. int LOG = ceil(log2(N)) + 1;
  67. m.resize(N, vector<int>(LOG, 0));
  68. for (int i{}; i < N; i++)
  69. m[i][0] = lcp[i];
  70. for (int k = 1; k < LOG; k++)
  71. {
  72. for (int i{}; i + (1 << k) - 1 < N; i++)
  73. m[i][k] = min(m[i][k - 1], m[i + (1 << (k - 1))][k - 1]);
  74. }
  75. }
  76. int query(int L, int R) // 0-based
  77. {
  78. if (L == R)
  79. return N - L - 1;
  80. L = pos[L], R = pos[R];
  81. if (L > R)
  82. swap(L, R);
  83. R--;
  84. int len = R - L + 1;
  85. assert(len > 0);
  86. int k = 31 - clz(len);
  87. return min(m[L][k], m[R - (1 << k) + 1][k]);
  88. }
  89. }
  90. using namespace SuffixArray;
  91.  
  92. bool compare(const pair<int, int> &P1, const pair<int, int> &P2)
  93. {
  94. const auto &[i, j] = P1;
  95. const auto &[k, l] = P2;
  96. int len1 = j - i + 1, len2 = l - k + 1;
  97.  
  98. int LCP = query(i, k);
  99. if (LCP >= min(len1, len2))
  100. {
  101. if (len1 == len2) // The two strings are equal
  102. {
  103. if (i != k)
  104. return i < k;
  105. return j <= l;
  106. }
  107. return len1 < len2;
  108. }
  109. return S[i + LCP] <= S[k + LCP];
  110. }
  111.  
  112. int main()
  113. {
  114. ios_base::sync_with_stdio(false);
  115. cin.tie(nullptr);
  116. #ifndef ONLINE_JUDGE
  117. freopen("input.txt", "r", stdin);
  118. freopen("Output.txt", "w", stdout);
  119. #endif //! ONLINE_JUDGE
  120. int t = 1;
  121. ll N, Q;
  122. // cin >> t;
  123. while (t--)
  124. {
  125. cin >> S;
  126. S.push_back(' ');
  127. buildSA();
  128. buildLCP();
  129.  
  130. cin >> Q;
  131. vector<pair<int, int>> vc;
  132. while (Q--)
  133. {
  134. int L, R;
  135. cin >> L >> R;
  136. vc.push_back({--L, --R});
  137. }
  138. sort(vc.begin(), vc.end(), compare);
  139. for (auto &[l, r] : vc)
  140. cout << ++l << " " << ++r << endl;
  141. }
  142. return 0;
  143. }
Success #stdin #stdout #stderr 0.22s 40196KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
Error: unexpected symbol in "using namespace"
Execution halted