Codeforces Round 621 (Div. 1 + Div. 2) |
---|
Закончено |
Корова Бесси только что перехватила сообщение, которое Фермер Джон отправил Бургер Куин! Бесси уверена, что в нем скрыто секретное сообщение.
Сообщение представляет из себя строку $$$s$$$, состоящую из строчных букв латинского алфавита. Бесси считает, что строка $$$t$$$ скрыта в строке $$$s$$$, если $$$t$$$ является подпоследовательностью $$$s$$$, индексы которой формируют арифметическую прогрессию. Например, строка aab скрыта в строке aaabb, потому что она получена в индексах $$$1$$$, $$$3$$$ и $$$5$$$, которые формируют арифметическую прогрессию с шагом $$$2$$$. Бесси считает, что любая скрытая строка, которая имеет наибольшее количество вхождений и является скрытым сообщением. Два вхождения подпоследовательности $$$S$$$ различны, если различаются их множества индексов. Помогите Бесси узнать количество вхождений скрытого сообщения!
Например, в строке aaabb, a скрыта $$$3$$$ раза, b скрыта $$$2$$$ раза, ab скрыта $$$6$$$ раз, aa скрыта $$$3$$$ раза, bb скрыта $$$1$$$ раз, aab скрыта $$$2$$$ раза, aaa скрыта $$$1$$$ раз, abb скрыта $$$1$$$ раз, aaab скрыта $$$1$$$ раз, aabb скрыта $$$1$$$ раз и aaabb скрыта $$$1$$$ раз. Количество вхождений скрытого сообщения равно $$$6$$$.
В первой строке задана строка $$$s$$$, состоящая из строчных букв латинского алфавита ($$$1 \le |s| \le 10^5$$$) — текст, который перехватила Бесси.
Выведите единственное число — количество вхождений секретного сообщения.
aaabb
6
usaco
1
lol
2
В первом примере скрыты следующие строки (с соответствующими множествами индексов):
Во втором примере, ни одна скрытая строка не встречается более одного раза.
В третьем примере, скрытым сообщением является одна буква l.
Название |
---|