@algorithm.ts/manacher

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]
  }

Related

• 最长回文子串 Manacher 算法