Les palindromes sont amusants, mais certaines des autres cordes commencent à se sentir exclues. Nous pouvons transformer ces cordes en palindromes volumineux en les divisant en tableaux palindromiques de morceaux.

Par exemple, la chaîne "abcabca"n'est pas un palindrome si nous la lisons caractère par caractère, mais nous avons trois façons différentes d'en faire un palindrome volumineux :

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

Comme vous pouvez le voir, la palindromicité chunky est un concept très inclusif; chaque chaîne peut être transformée en un palindrome trapu d'au moins une manière.

Tâche

Ecrivez un programme ou une fonction qui reçoit une chaîne en entrée et renvoie sa grosseur palindromique , c'est-à-dire le nombre de ses partitions qui sont des tableaux palindromiques.

Cas de test

 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"

Règles supplémentaires

Vous pouvez supposer que l'entrée sera composée de 42 caractères ASCII imprimables ou moins, éventuellement entourés par des délimiteurs de chaîne de votre langue et / ou suivis d'une nouvelle ligne.
Pour chaque chaîne d'entrée valide, votre code doit se terminer en moins d'une minute sur ma machine (Intel Core i7-3770, 16 Go de RAM, Fedora 21).

Avec un algorithme adéquat, il devrait être facile de respecter ce délai. Cependant, vous ne pourrez probablement pas parcourir toutes les partitions de la chaîne d'entrée.
Si vous choisissez d'imprimer la sortie sur STDOUT, elle peut être suivie d'une seule nouvelle ligne.
Les règles de code-golf standard s'appliquent.

code-golf string palindrome set-partitions Dennis
la source

4

Pyth, 40 34 27 22 octets

Lhsmy:bd_df!xb>TbS/lb2

Essayez-le dans l'interpréteur en ligne .

Fortement golfé depuis la version initiale de 40 octets. Merci à FryAmTheEggman d'avoir signalé quelques opérateurs utiles (les documents sont difficiles à rechercher!) Qui m'ont fait économiser 6 octets au total. Merci à Dennis pour une économie intelligente d'un seul octet en interprétant le résultat xcomme une valeur véridique / fausse plutôt qu'un index - !xb>Tbplutôt que q<bT>Tb.

Comment ça fonctionne:

Nous définissons une fonction yqui détermine la grosseur d'une chaîne ben s'appelant récursivement sur des sous-chaînes de b. Les fonctions sont automatiquement mémorisées en Pyth, donc la récursivité a très peu de temps en termes de temps.

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)

Sam Cappleman-Lynes
la source

Oui, la plupart de l'apprentissage de Pyth est communal / essai et erreur / lecture du lexer, bon travail avec le golf beaucoup plus! :)

FryAmTheEggman

1

1. Vous pouvez enregistrer deux octets en soumettant la fonction. Pas besoin de l'appeler avec yz. 2. Au lieu de deux cartes et d'un filtre, vous pouvez utiliser une seule carte et une conditionnelle ( lien ), qui économise trois octets.

Dennis

2

CJam ( 41 39 octets)

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

Démo en ligne

C'est "impatient" dans le sens où il trouve le nombre de palindromes volumineux pour chaque chaîne "centrale" (c'est-à-dire le résultat de la suppression du même nombre de caractères aux deux extrémités de la chaîne d'origine), mais parce qu'il utilise l'auto-mémoising jL'opérateur est calculé une seule fois, ce qui donne un programme très rapide (et enregistre quelques caractères sur une implémentation non mémorisée).

Merci à Dennis pour une économie d'un octet.

Peter Taylor
la source

1

Mathematica, 77 72 57 octets

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

alephalpha
la source

1

Perl, 86 octets

Code 84 octets + 2 commutateurs

Il DOIT y avoir une méthode plus courte, mais voici:

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

Prend l'entrée de STDIN, une chaîne par ligne.

Explication: pour les valeurs 1<=$i<length(input string), utilise l'expression régulière /^(.{$i})(.*)\1$/pour obtenir les segments gauche et droit et incrémente le nombre. Puis fait de même récursivement pour la partie centrale de la chaîne.

svsd
la source

Palindromes volumineux