Модуль: Хеширование


Задача

7 /8


Культурный контакт

Теория Нажмите, чтобы прочитать/скрыть

Помимо последовательностей можно также хэшировать множества. То есть наборы объектов без порядка на них. Считается он по следующей формуле:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- считая все по модулю mod
где ord - функция, которая сопоставляет объекту множества его абсолютный порядковый номер среди всех возможных объектов (например, если объекты - натуральные числа, то ord(x) = x, а если строчные латинские буквы, то ord('a') = 1, ord('b') = 2 и т.д.)

То есть каждому объекту мы сопоставляем величину равную основанию в степени номера этого объекта и суммируем все эти величины для того, чтобы получить хэш всего множества. Как понятно из формулы, хэш легко пересчитывается, если в множество добавляется элемент или удаляется из него (просто добавляем или вычитаем необходимую величину). Такая же логика,  если добавляются или удаляются не одиночные элементы, а другие множества (просто добавляем/вычитаем их хэш).

Как вы уже могли понять, одиночные элементы рассматриваются как множества размера 1, для которых мы умеем считать хэш. А более крупные множества просто являются объединением таким единичных множеств, где объединяя множества, мы складываем их хэши.

На самом деле это все тот же полиномиальный хэш, но раньше коэффициентом при pm у нас было значение элемента последовательности под номером n - m - 1 (где n - длина последовательности), а теперь это количество элементов в множестве, у которых абсолютный порядковый номер равен m.

В таком хэшировании необходимо брать достаточно большое основание (большее, чем максимальный размер множества), либо использовать двойное хэширование, чтобы избежать ситуаций, когда множество из p объектов с абсолютным порядковым номером m имеюют тот же хэш, что и множество с одним объектом с абсолютным порядковым номером m+1.
 

Задача

В начале XVIII века группа европейских исследователей прибыла на остров, населённый группой племён, никогда не вступавших в контакт с представителями европейской цивилизации.

Для успешного налаживания контактов с аборигенами руководитель группы планирует делать подарок вождю каждого встреченного племени. С этой целью он привёз длинную цепочку из стекляшек, похожих на драгоценные камни. 
Представим цепочку как строку s, состоящую из маленьких букв английского алфавита, где каждая буква означает тип кусочка стекла на соответствующей позиции. 
Исследователи собираются разрезать цепочку на некоторые фрагменты, после чего вручать ровно один фрагмент вождю каждого встреченного группой племени. Руководитель исследователей решил разделить цепочку на фрагменты согласно следующим правилами:
  • Чтобы не тратить на разрезания много времени, каждый фрагмент должен являться группой соседних стекляшек цепочки, то есть подстрокой строки s.
  • Все стекляшки должны быть использованы, то есть каждая стекляшка должна оказаться включённой ровно в один фрагмент.
  • Поскольку исследователи не знают, как аборигены оценят те или иные виды стекляшек, они хотят, чтобы каждому вождю достался один и тот же набор стекляшек без учёта порядка. Иными словами, для любого типа стекляшек количество стекляшек этого типа должно быть одинаковым в каждом из фрагментов.
  • Исследователи не знают, сколько племён обитает на острове, поэтому количество подготовленных фрагментов должно быть максимальным.

Помогите руководителю определить максимальное количество фрагментов, которое может получиться.

Входные данные:
В первой строке дана строка s (1 <= |s| <= 5000000).

Выходные данные:
Выведите одно число - максимально возможное количество фрагментов, на которое исследователи могут разрезать имеющуюся у них цепочку, не нарушая ни одного из условий, сформулированных руководителем группы.

Примеры:
 
Входные данные Выходные данные
abbabbbab 3
aabb 1

Пояснения:
В первом примере исследователи могут разбить цепочку 'abbabbbab' на фрагменты 'abb', 'abb', 'bab', тогда вождю каждого встреченного ими племени достанется по одной стекляшке типа 'a' и по две стекляшки типа 'b'.

Во втором примере строку невозможно поделить цепочку больше чем на один фрагмент, соблюдая все условия.

time 1000 ms
memory 128 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Напишите программу

или выберите язык программирования и введите исходный код

Auto

       

Результат проверки программы 
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!