Shortest Palindrome

export function shortestPalindrome(s: string): string {
  const n = s.length;
  const reversed = toReversed(s);
  for (let i = 0; i <= n; i++) {
    if (s.startsWith(reversed.slice(i))) {
      return reversed.slice(0, i) + s;
    }
  }
  return '';
}
 
function toReversed(str: string): string {
  return [...str].reverse().join('');
}

export function shortestPalindrome(s: string): string {
  const n = s.length;
  const reversed = toReversed(s);
  const combined = `${s}#${reversed}`;
  const prefixTable = createPrefixTable(combined);
  const palindromeLength = prefixTable[prefixTable.length - 1];
  const suffix = reversed.slice(0, n - palindromeLength);
  return suffix + s;
}
 
function toReversed(str: string): string {
  return [...str].reverse().join('');
}
 
function createPrefixTable(str: string): number[] {
  const prefixTable = new Array<number>(str.length).fill(0);
  for (let i = 1, l = 0; i < str.length; i++) {
    while (0 < l && str[i] !== str[l]) {
      l = prefixTable[l - 1];
    }
    if (str[i] === str[l]) {
      l += 1;
    }
    prefixTable[i] = l;
  }
  return prefixTable;
}

export function shortestPalindrome(s: string): string {
  if (s.length === 0) {
    return s;
  }
  const modified = `^#${[...s].join('#')}#$`;
  const n = modified.length;
  const radius = new Array<number>(n).fill(0);
 
  let centerIndex = 0;
  let rightBoundary = 0;
  let maxPalindromeLength = 0;
 
  for (let i = 1; i < n - 1; i++) {
    const mirrorIndex = 2 * centerIndex - i;
    if (i < rightBoundary) {
      radius[i] = Math.min(rightBoundary - i, radius[mirrorIndex]);
    }
 
    while (modified[i + 1 + radius[i]] === modified[i - 1 - radius[i]]) {
      radius[i] += 1;
    }
 
    if (i + radius[i] > rightBoundary) {
      centerIndex = i;
      rightBoundary = i + radius[i];
    }
 
    if (i - radius[i] === 1) {
      maxPalindromeLength = Math.max(maxPalindromeLength, radius[i]);
    }
  }
  const suffix = s.slice(maxPalindromeLength);
  return toReversed(suffix) + s;
}
 
function toReversed(str: string): string {
  return [...str].reverse().join('');
}