1function buildSuffixArray(s) {
2 const n = s.length;
3 let rank = [...s].map((c) => c.charCodeAt(0));
4 let sa = [...Array(n).keys()].sort((a, b) => rank[a] - rank[b] || a - b);
5 const tmp = new Array(n).fill(0);
6 for (let k = 1; k < n; k *= 2) {
7 const rk = (i) => (i < n ? rank[i] : -1);
8 sa.sort((a, b) => rk(a) - rk(b) || rk(a + k) - rk(b + k));
9 tmp[sa[0]] = 0;
10 for (let i = 1; i < n; i++)
11 tmp[sa[i]] = tmp[sa[i - 1]] + (rk(sa[i]) !== rk(sa[i - 1]) || rk(sa[i] + k) !== rk(sa[i - 1] + k) ? 1 : 0);
12 rank = [...tmp];
13 if (rank[sa[n - 1]] === n - 1) break;
14 }
15 return sa;
16}
17function buildHeight(s, sa) {
18 const n = s.length;
19 const rank = new Array(n);
20 sa.forEach((v, i) => (rank[v] = i));
21 const height = new Array(n).fill(0);
22 let h = 0;
23 for (let i = 0; i < n; i++) {
24 if (rank[i] === 0) { h = 0; continue; }
25 const j = sa[rank[i] - 1];
26 while (s[i + h] === s[j + h]) h++;
27 height[rank[i]] = h;
28 if (h > 0) h--;
29 }
30 return height;
31}