Palindrom memang menyenangkan, tetapi beberapa senar lainnya mulai merasa ditinggalkan. Kita dapat mengubah string-string itu menjadi palindrom tebal dengan memecahnya menjadi susunan palindromik.

Misalnya, string "abcabca"bukan palindrome jika kita membacanya karakter demi karakter, tetapi kita memiliki tiga cara berbeda untuk menjadikannya palindrom tebal :

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

Seperti yang Anda lihat, palindromicness tebal adalah konsep yang sangat inklusif; setiap string dapat diubah menjadi palindrom tebal setidaknya dalam satu cara.

Tugas

Tulis program atau fungsi yang menerima string sebagai input dan mengembalikan chunkiness palindromiknya , yaitu jumlah partisi yang merupakan array palindromik.

Uji kasus

 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"

Aturan tambahan

Anda dapat berasumsi bahwa input terdiri dari 42 atau kurang karakter ASCII yang dapat dicetak, secara opsional dikelilingi oleh pembatas string bahasa Anda dan / atau diikuti oleh baris baru.
Untuk setiap string input yang valid, kode Anda harus selesai dalam waktu kurang dari satu menit di mesin saya (Intel Core i7-3770, 16 GiB RAM, Fedora 21).

Dengan algoritma yang memadai, seharusnya mudah untuk mematuhi batas waktu ini. Namun, Anda kemungkinan besar tidak akan dapat mengulangi semua partisi dari string input.
Jika Anda memilih untuk mencetak output ke STDOUT, mungkin diikuti oleh satu baris baru.
Aturan standar kode-golf berlaku.

code-golf string palindrome set-partitions Dennis
sumber

4

Pyth, 40 34 27 22 byte

Lhsmy:bd_df!xb>TbS/lb2

Cobalah di penerjemah online .

Sangat turun dari versi 40 byte awal. Terima kasih kepada FryAmTheEggman karena menunjukkan beberapa operator yang berguna (dokumen sulit dicari!) Yang telah menyelamatkan saya total 6 byte. Terima kasih kepada Dennis untuk penghematan byte tunggal yang cerdas dengan menginterpretasikan hasil xsebagai nilai true / falsy daripada indeks - !xb>Tbbukan q<bT>Tb.

Bagaimana itu bekerja:

Kami mendefinisikan fungsi yyang menentukan chunkiness string bdengan secara rekursif menyebut dirinya pada substring dari b. Fungsi secara otomatis direkam dalam Pyth, sehingga rekursi memiliki overhead yang sangat sedikit dalam hal waktu.

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
sumber

Ya, sebagian besar belajar Pyth adalah komunal / coba-coba / baca lexer, kerja bagus dengan bermain golf jauh lebih banyak! :)

FryAmTheEggman

1

1. Anda dapat menyimpan dua byte dengan mengirimkan fungsi. Tidak perlu menyebutnya yz. 2. Alih-alih dua peta dan filter, Anda bisa menggunakan peta tunggal dan kondisional ( tautan ), yang menghemat tiga byte.

Dennis

2

CJam ( 41 39 byte)

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

Demo online

Ini "bersemangat" dalam arti bahwa ia menemukan jumlah palindrom tebal untuk setiap string "sentral" (yaitu hasil dari menghilangkan jumlah karakter yang sama dari kedua ujung string asli), tetapi karena ia menggunakan auto-memoising jmasing-masing operator dihitung sekali saja, memberikan program yang sangat cepat (dan menyimpan beberapa karakter di atas implementasi yang tidak di-memoised).

Terima kasih kepada Dennis untuk penghematan satu byte.

Peter Taylor
sumber

1

Mathematica, 77 72 57 byte

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

alephalpha
sumber

1

Perl, 86 byte

84 byte kode + 2 sakelar

Pasti ada metode yang lebih pendek, tetapi begini:

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

Mengambil input dari STDIN, satu string per baris.

Penjelasan: Untuk nilai 1<=$i<length(input string), gunakan regex /^(.{$i})(.*)\1$/untuk mendapatkan potongan kiri dan kanan dan menambah hitungan. Kemudian secara rekursif melakukan hal yang sama untuk bagian tengah string.

svsd
sumber

Palindrom tebal