Question

У Рахмана есть строка A из строчных букв. Он придумал особую формулу, по которой он находит Рахманов ломтик строки. Рахманов ломтик строки - это любая строка входящая в A максимальное количество раз. Найдите Рахманов ломтик строки A Входные данные В первой и единственной строке дается строка A . Длина строки не превышает 10 5 Выходные данные Выведите Рахманов Ломтик строки A . Примеры входные данные afaf выходные данные af входные данные bakbak выходные данные bak

Answer 1

Для решения этой задачи можно воспользоваться алгоритмом, который позволит найти Рахманов ломтик строки A. Мы можем перебрать все возможные подстроки строки A и посчитать, сколько раз каждая подстрока встречается в исходной строке. Затем выберем ту подстроку, которая встречается максимальное количество раз.

Давайте рассмотрим псевдокод для данного алгоритма:

1. Инициализируем словарь (map) для хранения подстрок и их частоты в строке A.
2. Перебираем все возможные подстроки строки A и для каждой подстроки:
   • Если она уже есть в словаре, увеличиваем её частоту на 1.
   • Если её нет в словаре, добавляем её туда с частотой 1.
3. Находим подстроку с максимальной частотой в словаре.
4. Это и будет Рахманов ломтик строки A.

Применим этот алгоритм на примерах:

Пример 1: Входные данные: afaf

1. Перебираем все подстроки: "a", "af", "f", "af", "fa", "afaf".
2. Считаем частоту каждой подстроки: "a": 2, "af": 2, "f": 1, "fa": 1, "afaf": 1.
3. Подстроки "a" и "af" имеют максимальную частоту (2).
4. Результат: Рахманов ломтик строки A - "af".

Пример 2: Входные данные: bakbak

1. Перебираем все подстроки: "b", "ba", "bak", "a", "ak", "bakb", "a", "ak", "k", "bakba", "a", "ak", "k", "bakbak".
2. Считаем частоту каждой подстроки: "b": 2, "ba": 2, "bak": 2, "a": 2, "ak": 2, "bakb": 1, "bakba": 1, "bakbak": 1.
3. Подстроки "b", "ba", "bak", "a", и "ak" имеют максимальную частоту (2).
4. Результат: Рахманов ломтик строки A - "bak".

Таким образом, ответ на входные данные "afaf" - "af", а на входные данные "bakbak" - "bak".