fork download
  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
stdin
8 3
aabaabab
1 4
2 3
3 2

stdout
  1 : aabaabab
  2 : aabab
  3 : ab
  4 : abaabab
  5 : abab
  6 : b
  7 : baabab
  8 : bab
  aabaabab
  aabab
  abaabab
  abab
  baabab
  bab