Manacher's algorithm

[pathikrit]

// O(n^3) version
def countPalindromes3(s: String): Int =
  (1 to s.length).flatMap(s.sliding).count(t => t.reverse == t)

// O(n^2) version
def countPalindromes2(s: String): Int = {

  def countBetween(left: Int, right: Int): Int = {
    if (s.isDefinedAt(left) && s.isDefinedAt(right) && s(left) == s(right)) {
      1 + countBetween(left - 1, right + 1)
    } else {
      0
    }
  }

  s.indices.map(i => countBetween(left = i, right = i) + countBetween(left = i, right = i+1)).sum
}

// O(n) version
def countPalindromes1(s: String): Int = {
  // Manacher's algo - non trivial
  ???
}```