Courses

Algorithms

Hashing

Module: Hashing

Problem

7 /8

cultural contact

Theory Click to read/hide

In addition to sequences, you can also hash sets. That is, sets of objects with no order on them. It is calculated according to the following formula:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\) <- counting everything modulo
where ord is a function that assigns to an object of the set its absolute ordinal number among all possible objects (for example, if the objects are natural numbers, then ord(x) = x, and if lowercase Latin letters, then ord('a' ;) = 1, ord('b') = 2 etc.)

That is, for each object we associate a value equal to the base to the power of the number of this object and sum up all these values in order to obtain a hash of the entire set. As is clear from the formula, the hash is easily recalculated if an element is added to or removed from the set (just add or subtract the required value). Same logic, if not single elements are added or removed, but other sets (just add / subtract their hash).

As you can already understand, single elements are considered as sets of size 1, for which we can calculate the hash. And larger sets are simply a union of such single sets, where by combining sets, we add their hashes.

In fact, this is still the same polynomial hash, but before the coefficient at p^m , we had the value of the sequence element under number n - m - 1 (where n is the length of the sequence), and now this is the number of elements in the set whose absolute ordinal number is equal to m.

In such hashing, one must take a sufficiently large base (larger than the maximum set size), or use double hashing to avoid situations where a set of p objects with absolute ordinal number m has the same hash as a set with one object with absolute ordinal number m+1.

Problem

At the beginning of the 18th century, a group of European explorers arrived on an island inhabited by a group of tribes that had never come into contact with representatives of European civilization.

To successfully establish contacts with the natives, the leader of the group plans to give a gift to the leader of each tribe he meets. To this end, he brought a long chain of glass, similar to precious stones.
Let's represent the string as a string s, consisting of small letters of the English alphabet, where each letter means the type of piece of glass at the corresponding position.
The researchers are going to cut the chain into some fragments, and then hand over exactly one fragment to the leader of each tribe encountered by the group. The research leader decided to split the chain into fragments according to the following rules:

In order not to spend a lot of time on cutting, each fragment should be a group of adjacent pieces of glass in the chain, that is, a substring of the string s.
All pieces of glass must be used, that is, each piece of glass must be included in exactly one fragment.
Because the researchers don't know how the aborigines will value certain types of glass, they want each chief to get the same set of glass without regard to order. In other words, for any type of glass, the number of glass of this type must be the same in each of the fragments.
Researchers don't know how many tribes live on the island, so the number of prepared fragments should be as large as possible.

Help the manager determine the maximum number of fragments that can be obtained.

Input:
The first line contains the string s (1 <= |s| <= 5000000).

Output:
Print a single number - the maximum possible number of fragments into which the researchers can cut the chain they have without violating any of the conditions formulated by the group leader.

Examples:

Input	Output
abbabbbab	3
aabb	1

Explanations:
In the first example, researchers can break the chain 'abbabbbab' fragments 'abb', 'abb', 'bab', then the leader of each tribe they meet will get one glass of type 'a' and two pieces of 'b'.

In the second example, the string cannot be divided into more than one fragment of the chain, observing all the conditions.

time 1000 ms
memory 128 Mb
Rules for program design and list of errors in automatic problem checking