Палиндромы - это весело, но некоторые другие нити начинают чувствовать себя обделенными. Мы можем превратить эти строки в короткие палиндромы , разбив их на палиндромные массивы частей.
Например, строка "abcabca"
не является палиндромом, если мы читаем ее символ за символом, но у нас есть три различных способа сделать ее коротким палиндромом:
["abcabca"]
["a" "bcabc" "a"]
["a" "bc" "a" "bc" "a"]
Как видите, коренастая палиндромность - это очень всеобъемлющее понятие; каждая строка может быть превращена в коренастый палиндром хотя бы одним способом.
задача
Напишите программу или функцию, которая получает строку в качестве входных данных и возвращает ее палиндромный массив , т. Е. Количество его разделов, которые являются палиндромными массивами.
Контрольные примеры
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"
Дополнительные правила
Вы можете предполагать, что ввод будет состоять из 42 или менее печатных символов ASCII, опционально окруженных разделителями строк вашего языка и / или сопровождаемых новой строкой.
Для каждой допустимой входной строки ваш код должен завершиться менее чем за одну минуту на моем компьютере (Intel Core i7-3770, 16 ГБ ОЗУ, Fedora 21).
С адекватным алгоритмом должно быть легко соответствовать этому временному пределу. Однако вы, скорее всего, не сможете перебирать все разделы входной строки.
Если вы решите распечатать вывод в STDOUT, за ним может следовать одна новая строка.
Применяются стандартные правила игры в гольф .
yz
. 2. Вместо двух карт и фильтра вы можете использовать одну карту и условную ( ссылку ), которая сохраняет три байта.CJam (
4139 байт)Онлайн демо
Это «нетерпение» в том смысле, что оно находит количество длинных палиндромов для каждой «центральной» строки (т. Е. Результат удаления одинакового количества символов с обоих концов исходной строки), но потому, что оно использует автозаписывание
j
Оператор каждого вычисляется только один раз, давая очень быструю программу (и сохраняя несколько символов в незапамятной реализации).Спасибо Деннису за сохранение одного байта.
источник
Mathematica,
777257 байтисточник
Perl, 86 байт
Код 84 байта + 2 переключателя
Должен быть более короткий метод, но здесь идет:
Принимает ввод из STDIN, по одной строке на строку.
Объяснение: Для значений
1<=$i<length(input string)
используется регулярное выражение/^(.{$i})(.*)\1$/
для получения левого и правого фрагментов и увеличения счетчика. Затем рекурсивно делает то же самое для центральной части строки.источник