| 22 | } |
| 23 | |
| 24 | std::vector<int> lcp_naive(std::vector<int> s, std::vector<int> sa) { |
| 25 | int n = int(s.size()); |
| 26 | assert(n); |
| 27 | std::vector<int> lcp(n - 1); |
| 28 | for (int i = 0; i < n - 1; i++) { |
| 29 | int l = sa[i], r = sa[i + 1]; |
| 30 | while (l + lcp[i] < n && r + lcp[i] < n && s[l + lcp[i]] == s[r + lcp[i]]) lcp[i]++; |
| 31 | } |
| 32 | return lcp; |
| 33 | } |
| 34 | |
| 35 | std::vector<int> z_naive(std::vector<int> s) { |
| 36 | int n = int(s.size()); |