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 .
yz
. 2. Zamiast dwóch map i filtra można użyć jednej mapy i warunkowego ( link ), który oszczędza trzy bajty.CJam (
4139 bajtów)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
j
każ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.
źródło
Mathematica,
777257 bajtówźródło
Perl, 86 bajtów
Kod 84 bajtów + 2 przełączniki
Musi być krótsza metoda, ale oto:
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.źródło