410529: GYM104035 4 Браслет

Memory Limit:0 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

4. Браслетограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Варе подарили на День Рождения браслет, на котором по кругу записаны строчные английские буквы. Изучив внимательно браслет, Варя поняла, что на нём написано какое-то слово тарабарского языка состоящее из $$$N$$$ букв. Особенность слов тарабарского языка в том, что в них всегда от одной до восьми букв «a».

Подумав, Варя решила, что ей не нужен браслет, а нужна цепочка. И для этого ей нужно разрезать браслет ровно в одном месте, чтобы получившееся слово было палиндромом. Помогите Варе, подсчитайте, сколько есть способов разрезать браслет так, чтобы получилось слово-палиндром и определите позиции возможных разрезов — номера букв, после которых можно разрезать браслет (буквы в слове пронумерованы от $$$1$$$ до $$$N$$$).

Браслет из первого теста.

Для справки: палиндром — слово, одинаково читающееся в обоих направлениях, например «abba».

Входные данные

Первая строка содержит целое число $$$N$$$ ($$$1 \le N \le 2 \cdot 10^6$$$) — длину слова на тарабарском языке.

Вторая строка содержит последовательность из $$$N$$$ строчных букв английского алфавита — слово на тарабарском языке.

Выходные данные

В первой строке выведите целое число $$$K$$$ — количество способов разрезать браслет.

В следующих $$$K$$$ строках выведите позиции возможных разрезов. Выводить позиции можно в любом порядке.

Система оценки

В этой задаче 28 тестов, не считая тестов из условия. Каждый тест будет оцениваться независимо.

Решения, правильно работающие при $$$N \le 2000$$$, будут оцениваться в 36 баллов.

ПримерыВходные данные
4
abba
Выходные данные
2
2
4
Входные данные
5
arbat
Выходные данные
0
Примечание

В первом тесте разрезать браслет можно двумя способами. Можно сделать разрез между буквами $$$b$$$, тогда получится палиндром «baab», либо между буквами $$$a$$$, тогда получится палиндром «abba».

В втором тесте нельзя разрезать браслет так, чтобы получился палиндром.

加入题单

上一题 下一题 算法标签: