Skip to content

Latest commit

 

History

History
106 lines (90 loc) · 2.78 KB

README.md

File metadata and controls

106 lines (90 loc) · 2.78 KB

@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