1
var shortestPalindrome = function (s) {
2
  const rev = s.split("").reverse().join("");
3
  const slen = s.length;
4

5
  const z = s + "$" + rev;
6
  const zlen = z.length;
7

8
  const lpt = new Array(zlen).fill(0);
9

10
  for (let i = 1; i < zlen; i++) {
11
    let j = lpt[i - 1];
12

13
    while (j > 0 && z.charAt(i) != z.charAt(j)) j = lpt[j - 1];
14

15
    if (z.charAt(i) == z.charAt(j)) j++;
16

17
    lpt[i] = j;
18
  }
19

20
  return rev.slice(0, slen - lpt.at(-1)) + s;
21
};