fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "using namespace"
Execution halted
https://ideone.com/3djDlY
language:
R (R 3.5.2)
created:
26 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!