Palíndromos são divertidos, mas algumas das outras strings estão começando a parecer deixadas de fora. Podemos transformar essas cordas em palíndromos em pedaços dividindo-os em matrizes palindrômicas de pedaços.

Por exemplo, a string "abcabca"não é um palíndromo se a lermos caractere por caractere, mas temos três maneiras diferentes de torná-lo um palíndromo robusto :

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

Como você pode ver, palindromicidade robusta é um conceito muito inclusivo; toda corda pode ser transformada em um palíndromo robusto de pelo menos uma maneira.

Tarefa

Escreva um programa ou uma função que receba uma string como entrada e retorne sua robustez palindrômica , ou seja, o número de partições que são matrizes palindrômicas.

Casos de teste

 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"

Regras adicionais

Você pode assumir que a entrada consistirá em 42 ou menos caracteres ASCII imprimíveis, opcionalmente cercados pelos delimitadores de string do seu idioma e / ou seguidos por uma nova linha.
Para cada sequência de entrada válida, seu código deve terminar em menos de um minuto na minha máquina (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

Com um algoritmo adequado, deve ser fácil cumprir esse limite de tempo. No entanto, você provavelmente não conseguirá iterar em todas as partições da sequência de entrada.
Se você optar por imprimir a saída para STDOUT, ela poderá ser seguida por uma única nova linha.
Aplicam-se as regras de código-golfe padrão .

code-golf string palindrome set-partitions Dennis
fonte

4

Pitão, 40 34 27 22 bytes

Lhsmy:bd_df!xb>TbS/lb2

Experimente no intérprete online .

Fortemente jogado abaixo da versão inicial de 40 bytes. Obrigado a FryAmTheEggman por apontar alguns operadores úteis (é difícil pesquisar documentos!) Que me salvaram 6 bytes no total. Graças a Dennis para um único byte inteligente poupando ao interpretar o resultado de xque um valor truthy / Falsas vez de um índice - !xb>Tbem vez deq<bT>Tb .

Como funciona:

Definimos uma função yque determina a fragilidade de uma string bchamando-se recursivamente a si mesma nas substrings de b. As funções são automaticamente memorizadas no Pyth, portanto, a recursão tem muito pouco custo adicional em termos de tempo.

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
fonte

Sim, a maior parte do aprendizado de Pyth é comunitária / tentativa e erro / leitura do lexer, bom trabalho com o golfe muito mais! :)

FryAmTheEggman

1

1. Você pode salvar dois bytes enviando a função. Não há necessidade de chamá-lo yz. 2. Em vez de dois mapas e um filtro, você pode usar um único mapa e um condicional ( link ), que economiza três bytes.

Dennis

2

CJam ( 41 39 bytes)

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

Demonstração online

Isso é "ansioso" no sentido de encontrar o número de palíndromos robustos para cada sequência "central" (isto é, o resultado da remoção do mesmo número de caracteres de ambas as extremidades da sequência original), mas porque usa a memorização automática jcada operador é calculado apenas uma vez, fornecendo um programa muito rápido (e salvando alguns caracteres em uma implementação não memorizada).

Agradecimentos a Dennis pela economia de um byte.

Peter Taylor
fonte

1

Mathematica, 77 72 57 bytes

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

alefalpha
fonte

1

Perl, 86 bytes

Código de 84 bytes + 2 switches

Tem que haver um método mais curto, mas aqui vai:

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

Recebe entrada de STDIN, uma string por linha.

Explicação: Para valores 1<=$i<length(input string), use o regex /^(.{$i})(.*)\1$/para obter os pedaços esquerdo e direito e incrementa a contagem. Em seguida, recursivamente faz o mesmo para a parte central da string.

svsd
fonte

Palíndromos robustos