Корова Бесси только что перехватила сообщение, которое Фермер Джон отправил Бургер Куин! Бесси уверена, что в нем скрыто секретное сообщение.
Сообщение представляет из себя строку \(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\).
Примечание
В первом примере скрыты следующие строки (с соответствующими множествами индексов):
- a встречается как \((1)\), \((2)\), \((3)\);
- b встречается как \((4)\), \((5)\);
- ab встречается как \((1,4)\), \((1,5)\), \((2,4)\), \((2,5)\), \((3,4)\), \((3,5)\);
- aa встречается как \((1,2)\), \((1,3)\), \((2,3)\);
- bb встречается как \((4,5)\);
- aab встречается как \((1,3,5)\), \((2,3,4)\);
- aaa встречается как at \((1,2,3)\)
- abb встречается как \((3,4,5)\)
- aaab встречается как \((1,2,3,4)\);
- aabb встречается как \((2,3,4,5)\);
- aaabb встречается как \((1,2,3,4,5)\);
Заметим, что все множества индексов являются арифметическими прогрессиями.
Во втором примере, ни одна скрытая строка не встречается более одного раза.
В третьем примере, скрытым сообщением является одна буква l.