| 103 | build(); |
| 104 | } |
| 105 | void costruct_lcp() { |
| 106 | int k = 0; |
| 107 | lcp.resize(n - 1, 0); |
| 108 | for (int i = 0; i < n; i++) { |
| 109 | if (rank[i] == n - 1) { |
| 110 | k = 0; |
| 111 | continue; |
| 112 | } |
| 113 | int j = sa[rank[i] + 1]; |
| 114 | while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++; |
| 115 | lcp[rank[i]] = k; |
| 116 | if (k) k--; |
| 117 | } |
| 118 | } |
| 119 | void prec() { |
| 120 | lg.resize(n, 0); |
| 121 | for (int i = 2; i < n; i++) lg[i] = lg[i / 2] + 1; |