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
 ???
}```