Задача №114676. Гармоничные шарфы
Одного шарфа вам может не хватить, поэтому вы заинтересованы в полезных кусках ткани — непустых кусках, которые можно разделить на несколько непрерывных последовательностей полосок, являющихся гармоничными. Например, последовательности "ab" , "cbcac" являются полезными, так как их можно разделить на куски "ab" и "cbc":+:"ac" соответственно.
Посчитайте количество способов вырезать из вашей ткани непрерывный полезный кусок.
В первой строке входных данных вводится одно целое число \(n\) (\(1 \le n \le 1\,000\,000\)) — количество полосок в вашем куске ткани.
Во второй строке входных данных вводится строка \(s\) длины \(n\) — последовательность цветов полосок в вашей ткани.
Выведите одно целое число — количество полезных кусков в вашей ткани.
Во первом тесте из условия полезными являются куски "ba" , "ba" , "ab" , "bab" "aba" , "baba" .
Обратите внимание, что различные полезные куски могут совпадать как строки.
Во втором тесте из условия полезными являются куски "cb" , "cbc" , "bc" , "ca" , "cbca" .
Тесты к этой задаче состоят из 5 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Доп. ограничения | ||||
| Группа | Баллы | \(n\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | Тесты из условия. |
| 1 | 17 | \(n \le 500\) | 0 | |
| 2 | 14 | \(n \le 5000\) | 0 | \(s_i \ne s_{i - 1}\) |
| 3 | 19 | \(n \le 5000\) | 0, 1, 2 | |
| 4 | 21 | – | 0, 2 | \(s_i \ne s_{i - 1}\) |
| 5 | 29 | – | 0 – 4 |
4 baba
6
4 cbca
5