Palindrome machen Spaß, aber einige der anderen Saiten fühlen sich allmählich ausgelassen. Wir können diese Saiten in klobige Palindrome verwandeln, indem wir sie in palindrome Gruppen von Stücken aufteilen.

Beispielsweise ist der String "abcabca"kein Palindrom, wenn wir ihn Zeichen für Zeichen lesen, aber wir haben drei verschiedene Möglichkeiten, ihn zu einem klobigen Palindrom zu machen:

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

Wie Sie sehen können, ist klobige Palindromie ein sehr umfassendes Konzept. Jede Saite kann auf mindestens eine Weise in ein klobiges Palindrom verwandelt werden.

Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die eine Zeichenfolge als Eingabe empfängt und ihre palindromische Chunkiness zurückgibt , dh die Anzahl ihrer Partitionen, die palindromische Arrays sind.

Testfälle

 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"

Zusätzliche Regeln

• Sie können davon ausgehen, dass die Eingabe aus 42 oder weniger druckbaren ASCII-Zeichen besteht, die optional von den Zeichenfolgenbegrenzern Ihrer Sprache und / oder einer neuen Zeile umgeben sind.

• Für jede gültige Eingabezeichenfolge muss Ihr Code auf meinem Computer (Intel Core i7-3770, 16 GB RAM, Fedora 21) in weniger als einer Minute fertig sein.

  Mit einem geeigneten Algorithmus sollte es einfach sein, diese Frist einzuhalten. Höchstwahrscheinlich können Sie jedoch nicht alle Partitionen der Eingabezeichenfolge durchlaufen.

• Wenn Sie die Ausgabe auf STDOUT drucken möchten, wird möglicherweise eine einzelne neue Zeile eingefügt.

• Es gelten die Standardregeln für Code-Golf .

Pyth, 40 34 27 22 Bytes

Lhsmy:bd_df!xb>TbS/lb2

Probieren Sie es im Online-Dolmetscher aus .

Von der ursprünglichen 40-Byte-Version stark heruntergespielt. Vielen Dank an FryAmTheEggman für den Hinweis auf einige nützliche Operatoren (Dokumente sind schwer zu finden!), Mit denen ich insgesamt 6 Byte gespart habe. Dank Dennis für eine clevere einziges Byte sparen , indem das Ergebnis der Interpretation xals truthy / falsy Wert eher als ein Index - !xb>Tbstatt q<bT>Tb.

Wie es funktioniert:

Wir definieren eine Funktion, ydie die Chunkiness eines Strings bestimmt, bindem sie sich rekursiv auf Teilstrings von aufruft b. Funktionen werden automatisch in Pyth gespeichert, sodass die Rekursion nur einen geringen zeitlichen Aufwand verursacht.

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 Bytes)

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

Online-Demo

Dies ist "eifrig" in dem Sinne, dass es die Anzahl von klobigen Palindromen für jede "zentrale" Zeichenfolge findet (dh das Ergebnis des Entfernens der gleichen Anzahl von Zeichen von beiden Enden der ursprünglichen Zeichenfolge), aber weil es das automatische Merken verwendet jJeder Operator wird nur einmal berechnet, was ein sehr schnelles Programm ergibt (und einige Zeichen über eine nicht-memoisierte Implementierung speichert).

Vielen Dank an Dennis für die Einsparung von einem Byte.

Mathematica, 77 72 57 Bytes

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

Perl, 86 Bytes

84 Byte Code + 2 Schalter

Es muss eine kürzere Methode geben, aber hier geht es:

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

Übernimmt die Eingabe von STDIN, eine Zeichenfolge pro Zeile.

Erläuterung: 1<=$i<length(input string)Verwendet für Werte den regulären Ausdruck /^(.{$i})(.*)\1$/, um die linken und rechten Abschnitte abzurufen und die Anzahl zu erhöhen. Das Gleiche geschieht dann rekursiv für den mittleren Teil der Zeichenfolge.