Chunky palindromes

Question

Palindromes are fun, but some of the other strings are starting to feel left out. We can turn those strings into chunky palindromes by splitting them up into palindromic arrays of chunks.

For example, the string "abcabca" isn't a palindrome if we read it character by character, but we have three different ways of making it a chunky palindrome:

["abcabca"]
["a" "bcabc" "a"]
["a" "bc" "a" "bc" "a"]

As you can see, chunky palindromicness is a very inclusive concept; every string can be turned into a chunky palindrome in at least one way.

Task

Write a program or a function that receives a string as input and returns its palindromic chunkiness, i.e., the number of its partitions that are palindromic arrays.

Test cases

 OUTPUT | INPUT
--------+---------------------------------------------
      1 | ""                                          
      1 | "a"                                         
      1 | "ab"                                        
      2 | "aa"                                        
      2 | "aaa"                                       
      3 | "abcabca"                                   
      4 | "abababab"                                  
     28 | "abcabcaabababababcabca"                    
      1 | "bbbbabababbbbababbbaaaaa"                  
     20 | "ababbaaaabababbbaaabbbaa"                  
      5 | "baaabaabababaababaaabbaab"                 
     62 | "bbaaababbabbabbbabaabaabb"                 
      2 | "a man a plan a canal panama"               
     25 | "ama nap lan aca nal pan ama"               
     93 | "SATOR   AREPO   TENET   OPERA   ROTAS"     
    976 | "abcabcaabcabcaabcabcaabcabcaabcabcaabcabca"
  28657 | "ababababababababababaababababababababababa"
2097152 | "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

Additional rules

• You may assume that the input will consist of 42 or less printable ASCII characters, optionally surrounded by your language's string delimiters and/or followed by a newline.

• For each valid input string, your code must finish in less than one minute on my machine (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

  With an adequate algorithm, it should be easy to comply with this time limit. However, you will most likely not be able to iterate over all partitions of the input string.

• If you choose to print the output to STDOUT, it may be followed by a single newline.

• Standard code-golf rules apply.

Answer 1

Pyth, 40 34 27 22 bytes

Lhsmy:bd_df!xb>TbS/lb2

Try it in the online interpreter.

Heavily golfed down from initial 40 byte version. Thanks to FryAmTheEggman for pointing out a couple of useful operators (docs are hard to search!) that have saved me 6 bytes total. Thanks to Dennis for a clever single byte saving by interpreting the result of x as a truthy/falsy value rather than an index - !xb>Tb rather than q<bT>Tb.

---

How it works:

We define a function y which determines the chunkiness of a string b by recursively calling itself on substrings of b. Functions are automatically memoized in Pyth, so recursion has very little overhead in terms of time.

L                              def y(b): return ___
                 S/lb2         The range [1,2,...,len(b)/2]
          f!xb>Tb              Filter n for which b[:n] == b[-n:]
   m                           Map each n in the list to...
    y:bd_d                     y(b[d:-d])       
 hs                            Take the sum and add one (implicit return)

Answer 2

Pip, 98 66 bytes

-32 thanks to @DLosc!

k:{[[z:a]]AL$AL({b:zc:b@<aAL_M(kb@>a)z:bc}M@>(,#a))}#(_QRV_FI(ka))

My first Pip answer!

Answer 3

CJam (41 39 bytes)

qM{_,2/,\f{\~_2$>@2$<@~)/(@=\M*j*}1b)}j

Online demo

This is "eager" in the sense that it finds the number of chunky palindromes for each "central" string (i.e. the result of removing the same number of characters from both ends of the original string), but because it uses the auto-memoising j operator each is calculated once only, giving a very fast program (and saving a few characters over a non-memoised implementation).

Thanks to Dennis for a one byte saving.

Answer 4

Mathematica, 77 72 57 bytes

1+Tr[#0/@ReplaceList[#,{a__,b___,a__}:>{b}]]&@*Characters

Answer 5

Perl, 86 bytes

84 bytes code + 2 switches

There HAS to be a shorter method, but here goes:

perl -lpe 'sub c{my($x,$i)=@_;$x=~/^(.{$i})(.*)\1$/&&c($2,0*++$s)while++$i<length$x}c$_;$_=++$s'

Takes input from STDIN, one string per line.

Explanation: For values 1<=$i<length(input string), uses the regex /^(.{$i})(.*)\1$/ to get the left and right chunks and increments the count. Then recursively does the same for the center part of the string.