4.0.3 • Published 9 months ago

@algorithm.ts/manacher v4.0.3

Weekly downloads
-
License
MIT
Repository
github
Last release
9 months ago

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

4.0.3

9 months ago

4.0.2

10 months ago

4.0.1

1 year ago

4.0.0

1 year ago

3.1.1

2 years ago

3.1.0

2 years ago

3.0.0-alpha.8

2 years ago

3.0.0

2 years ago

3.0.0-alpha.7

2 years ago

3.0.0-alpha.6

3 years ago

3.0.0-alpha.3

3 years ago

3.0.0-alpha.2

3 years ago

3.0.0-alpha.5

3 years ago

3.0.0-alpha.4

3 years ago

3.0.0-alpha.1

3 years ago

3.0.0-alpha.0

3 years ago

2.0.14

3 years ago

2.0.13

3 years ago

2.0.12

3 years ago

2.0.8-alpha.0

3 years ago

2.0.7-alpha.1

3 years ago

2.0.7-alpha.0

3 years ago

2.0.5

3 years ago

2.0.4

3 years ago

2.0.11

3 years ago

2.0.7

3 years ago

2.0.6

3 years ago

2.0.9

3 years ago

2.0.10

3 years ago

2.0.8

3 years ago

2.0.3

3 years ago

2.0.2

3 years ago

2.0.0-alpha.0

3 years ago

2.0.1

3 years ago

1.0.24

3 years ago

2.0.0

3 years ago

1.0.23

4 years ago

1.0.22

4 years ago

1.0.21

4 years ago

1.0.20

4 years ago

1.0.19

4 years ago