@algorithm.ts/manacher NPM

A typescript implementation of the manacher algorithm.

Manacher is a linear time algorithm for listing all the palindromes that appear at the start of a given string.

If you are curious about this algorithm, you can visit here for more details.

Install

npm

npm install --save @algorithm.ts/manacher

yarn
```
yarn add @algorithm.ts/manacher
```

Usage

A solution of https://leetcode.com/problems/palindrome-partitioning-ii/

import manacher from '@algorithm.ts/manacher'

export function minCut(text: string): number {
  const N: number = text.length
  const radius: number[] = manacher(text)
  const dp: number[] = [0]

  for (let i = 1; i < N; ++i) {
    let answer: number = i < radius[i] * 2 ? 0 : dp[i - 1] + 1
    if (answer > 0) {
      for (let k = 1; k < i; ++k) {
        if (i - k < radius[i + k] * 2) {
          answer = Math.min(answer, dp[k - 1] + 1)
        }
      }
    }
    dp[i] = answer
  }
  return dp[N - 1]
}