fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. const int MN = 100005;
  6.  
  7. int N, M;
  8. char str[MN];
  9.  
  10. struct SuffixArray {
  11. 	int N, Str[MN], SA[MN], rk[MN], SA2[MN];
  12. 	int Sig, Buk[MN], Tmp[MN];
  13. 	int Height[MN];
  14.  
  15. 	inline void RSort() {
  16. 		for (int i = 1; i <= Sig; ++i) Buk[i] = 0;
  17. 		for (int i = 1; i <= N; ++i) ++Buk[rk[i]];
  18. 		for (int i = 1; i <= Sig; ++i) Buk[i] += Buk[i - 1];
  19. 		for (int i = N; i >= 1; --i) SA[Buk[rk[SA2[i]]]--] = SA2[i];
  20. 	}
  21.  
  22. 	inline void BuildSA() {
  23. 		/* Init Str */
  24. 		for (int i = 1; i <= N; ++i) rk[i] = Str[i], SA2[i] = i;
  25. 		rk[N + 1] = 0;
  26. 		Sig = 26 /* maximum letter in Str */, RSort();
  27. 		for (int j = 1; j < N; j <<= 1) {
  28. 			int P = 0;
  29. 			for (int i = 1; i <= j; ++i) SA2[++P] = N - j + i;
  30. 			for (int i = 1; i <= N; ++i) if (SA[i] > j) SA2[++P] = SA[i] - j;
  31. 			RSort();
  32. 			Tmp[SA[1]] = P = 1;
  33. 			for (int i = 2; i <= N; ++i) {
  34. 				if (rk[SA[i]] != rk[SA[i - 1]] || rk[SA[i] + j] != rk[SA[i - 1] + j]) ++P;
  35. 				Tmp[SA[i]] = P;
  36. 			}
  37. 			for (int i = 1; i <= N; ++i) rk[i] = Tmp[i];
  38. 			Sig = P;
  39. 			if (Sig == N) break;
  40. 		}
  41. 	}
  42.  
  43. 	inline void GetHeight() {
  44. 		int k = 0;
  45. 		for (int i = 1; i <= N; ++i) {
  46. 			if (rk[i] == 1) k = Height[1] = 0;
  47. 			else {
  48. 				if (k) --k;
  49. 				int j = SA[rk[i] - 1];
  50. 				while (i + k <= N && j + k <= N && Str[i + k] == Str[j + k]) ++k;
  51. 				Height[rk[i]] = k;
  52. 			}
  53. 		}
  54. 	}
  55.  
  56. 	int BLCP[MN][21], Bt;
  57.  
  58. 	inline void InitST() {
  59. 		for (int i = 1; i <= N; ++i) BLCP[i][0] = Height[i];
  60. 		while (2 << Bt <= N) ++Bt;
  61. 		for (int j = 1; j <= Bt; ++j)
  62. 			for (int i = 1 << j; i <= N; ++i)
  63. 				BLCP[i][j] = std::min(BLCP[i][j - 1], BLCP[i - (1 << (j - 1))][j - 1]);
  64. 	}
  65.  
  66. 	inline int LCP(int x, int y) {
  67. 		if (x == y) return N + 1;
  68. 		x = rk[x], y = rk[y];
  69. 		if (x > y) std::swap(x, y);
  70. 		int j = 31 - __builtin_clz(y - x);
  71. 		return std::min(BLCP[y][j], BLCP[x + (1 << j)][j]);
  72. 	}
  73.  
  74. 	inline void GetRange(int pos, int k, int &lb, int &rb) {
  75. 		int lj = 0;
  76. 		while (pos > 1 << lj && BLCP[pos][lj] >= k) ++lj;
  77. 		for (--lj, lb = pos; lj >= 0; --lj)
  78. 			if (lb > 1 << lj && BLCP[lb][lj] >= k)
  79. 				lb -= 1 << lj;
  80. 		int rj = 0;
  81. 		while (N - pos >= 1 << rj && BLCP[pos + (1 << rj)][rj] >= k) ++rj;
  82. 		for (--rj, rb = pos; rj >= 0; --rj)
  83. 			if (N - rb >= 1 << rj && BLCP[rb + (1 << rj)][rj] >= k)
  84. 				rb += 1 << rj;
  85. 	}
  86. } C1, C2;
  87.  
  88. int main() {
  89. 	scanf("%d%d", &N, &M);
  90. 	scanf("%s", str + 1);
  91. 	for (int i = 1; i <= N; ++i) C2.Str[N - i + 1] = C1.Str[i] = str[i] - 'a' + 1;
  92. 	C2.N = C1.N = N, C1.BuildSA(), C2.BuildSA(), C1.GetHeight(), C2.GetHeight(), C1.InitST(), C2.InitST();
  93. 	for (int i = 1; i <= N; ++i) printf("%3d : %s\n", i, str + C1.SA[i]);
  94. 	while (M--) {
  95. 		int pos, k;
  96. 		scanf("%d%d", &pos, &k);
  97. 		pos = C1.rk[pos];
  98. 		int lb, rb;
  99. 		C1.GetRange(pos, k, lb, rb);
  100. 		for (int i = lb; i <= rb; ++i)
  101. 			printf("  %s\n", str + C1.SA[i]);
  102. 	}
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
8 3
aabaabab
1 4
2 3
3 2
stdout
copy 
  1 : aabaabab
  2 : aabab
  3 : ab
  4 : abaabab
  5 : abab
  6 : b
  7 : baabab
  8 : bab
  aabaabab
  aabab
  abaabab
  abab
  baabab
  bab
https://ideone.com/RHDZdU
language:
C++14 (gcc 8.3)
created:
4 years 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!