Palindromy są zabawne, ale niektóre inne łańcuchy zaczynają czuć się pominięte. Możemy przekształcić te struny w masywne palindromy , dzieląc je na palindromiczne tablice kawałków.

Na przykład ciąg "abcabca"nie jest palindromem, jeśli czytamy go znak po znaku, ale mamy trzy różne sposoby, aby uczynić go masywnym palindromem:

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

Jak widać, masywna palindromiczność jest pojęciem bardzo inkluzywnym; każdy łańcuch można przekształcić w masywny palindrom na co najmniej jeden sposób.

Zadanie

Napisz program lub funkcję, która odbiera ciąg jako dane wejściowe i zwraca jego masę palindromiczną , tj. Liczbę jego partycji, które są tablicami palindromicznymi.

Przypadki testowe

 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"

Dodatkowe zasady

• Możesz założyć, że dane wejściowe będą się składały z 42 lub mniej znaków ASCII do wydrukowania, opcjonalnie otoczonych ogranicznikami napisów w Twoim języku i / lub po których będzie następował nowy wiersz.

• Dla każdego prawidłowego ciągu wejściowego kod musi zakończyć się w ciągu mniej niż jednej minuty na moim komputerze (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

  Przy odpowiednim algorytmie przestrzeganie tego terminu powinno być łatwe. Jednak najprawdopodobniej nie będziesz mógł iterować wszystkich partycji ciągu wejściowego.

• Jeśli zdecydujesz się wydrukować wyjście do STDOUT, po nim może być pojedyncza nowa linia.

• Obowiązują standardowe zasady gry w golfa .

Pyth, 40 34 27 22 bajtów

Lhsmy:bd_df!xb>TbS/lb2

Wypróbuj w tłumaczu online .

Mocno grał w golfa od początkowej 40-bajtowej wersji. Dzięki FryAmTheEggman za wskazanie kilku przydatnych operatorów (dokumentów trudno przeszukiwać!), Które zaoszczędziły mi łącznie 6 bajtów. Dzięki Dennisowi za sprytną oszczędność jednego bajtu, interpretując wynik xjako wartość prawdziwości / fałszu, a nie jako indeks - !xb>Tbzamiast q<bT>Tb.

Jak to działa:

Definiujemy funkcję, yktóra określa wielkość łańcucha bprzez rekurencyjne wywoływanie się na podciągach b. Funkcje są automatycznie zapamiętywane w Pyth, więc rekursja ma bardzo małe obciążenie czasowe.

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)

CJam ( 41 39 bajtów)

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

Demo online

Jest to „chętne” w tym sensie, że znajduje liczbę masywnych palindromów dla każdego „centralnego” łańcucha (tj. Wynik usunięcia tej samej liczby znaków z obu końców oryginalnego łańcucha), ale ponieważ korzysta z automatycznego zapamiętywania jkażdy operator jest obliczany tylko raz, co daje bardzo szybki program (i pozwala zaoszczędzić kilka znaków na implementacji niepamiętanej).

Dzięki Dennisowi za oszczędność jednego bajtu.

Mathematica, 77 72 57 bajtów

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

Perl, 86 bajtów

Kod 84 bajtów + 2 przełączniki

Musi być krótsza metoda, ale oto:

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

Pobiera dane wejściowe ze STDIN, jeden ciąg w wierszu.

Objaśnienie: W przypadku wartości 1<=$i<length(input string)używa wyrażenia regularnego, /^(.{$i})(.*)\1$/aby uzyskać lewą i prawą porcję i zwiększa liczbę. Następnie rekurencyjnie robi to samo dla środkowej części łańcucha.