foo.hs

{-
Write a function for retrieving the total number of substring palindromes. 
For example the input is 'abba' then the possible palindromes= a, b, b, a, bb, abba 
So the result is 6. 
-}

-- Bruteforce:
-- check every contiguous subsequence.
-- imaging placing ( ) around each subsequence. 
-- for n choices of ( there are n-1 choices of )
-- so O(n!).
--
-- Memoization:
-- if A[i..j] is a palindrome then
-- A[i-1..j+1] is if A[i-1] == A[j+1]
-- A[i-1..j] is if A[i-1] == A[j]
-- A[i..j+1] is if A[i] == A[j+1]
-- for every A[k] it's O(1) to check each possible
-- subsequence extending to either side. So it's O(n)
-- overall.
-- do this for each A[k] => O(n^2)

subpalindromes :: [Char] -> Int
subpalindromes str =
  let
    xs =
      Vector.fromList str
    n =
      Vector.length xs - 1
    -- construct table centered around k
    -- [ 0 .. k-i..k..k+i .. n ]
    -- for k-i >= 0 and k+i <= n, i <= k and i <= n-k
    table k =
      let
        m =
          min k (n-k)
        eq i =
          if arr Array.! (i-1) then 
            xs Vector.! (k-i) == xs Vector.! (k+i) ||
            xs Vector.! k     == xs Vector.! (k+i) ||
            xs Vector.! (k-i) == xs Vector.! k
          else
            False
        arr =
          Array.array (0,m) $
            (0, True) : [ (i, eq i)| i <- [1..m] ]
      in
        Array.elems arr
  in
    List.sum .
    fmap (List.length . List.filter (== True) . table) $
      [0..n]