Courses

thuật toán

băm

Module: băm

Problem

7 /8

tiếp xúc văn hóa

Theory Click to read/hide

Ngoài các chuỗi, bạn cũng có thể băm các tập hợp. Đó là, tập hợp các đối tượng không có thứ tự trên chúng. Nó được tính theo công thức sau:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\) <- đếm mọi thứ theo modulo
trong đó ord là một hàm gán cho một đối tượng của tập hợp số thứ tự tuyệt đối của nó trong số tất cả các đối tượng có thể (ví dụ: nếu các đối tượng là số tự nhiên thì ord(x) = x và nếu là chữ cái Latinh viết thường thì ord(& #39;a') = 1, ord('b') = 2, v.v.)

Nghĩa là, đối với mỗi đối tượng, chúng tôi liên kết một giá trị bằng cơ sở với lũy thừa của số lượng đối tượng này và tổng hợp tất cả các giá trị này để có được hàm băm của toàn bộ tập hợp. Như rõ ràng từ công thức, hàm băm dễ dàng được tính toán lại nếu một phần tử được thêm vào hoặc xóa khỏi tập hợp (chỉ cần cộng hoặc trừ giá trị được yêu cầu). Cùng logic, nếu không phải các phần tử đơn lẻ được thêm hoặc bớt, mà là các tập hợp khác (chỉ cần cộng/trừ hàm băm của chúng).

Như bạn có thể hiểu, các phần tử đơn lẻ được coi là bộ kích thước 1, mà chúng ta có thể tính toán hàm băm. Và các tập hợp lớn hơn chỉ đơn giản là sự kết hợp của các tập hợp đơn lẻ như vậy, trong đó bằng cách kết hợp các tập hợp, chúng tôi thêm giá trị băm của chúng.

Thực ra, đây vẫn là hàm băm đa thức như cũ, nhưng trước hệ số tại p^m , ta đã có giá trị của phần tử dãy dưới số n - m - 1 (với n là độ dài của dãy), và bây giờ đây là số phần tử trong tập hợp có số thứ tự tuyệt đối bằng m.

Trong quá trình băm như vậy, người ta phải lấy một cơ sở đủ lớn (lớn hơn kích thước đặt tối đa) hoặc sử dụng băm kép để tránh các tình huống trong đó một tập hợp các đối tượng p có số thứ tự tuyệt đối m có cùng hàm băm với một tập hợp có một đối tượng có số thứ tự tuyệt đối số thứ tự m+1.

Problem

Vào đầu thế kỷ 18, một nhóm các nhà thám hiểm châu Âu đã đặt chân đến một hòn đảo nơi sinh sống của một nhóm bộ lạc chưa từng tiếp xúc với các đại diện của nền văn minh châu Âu.

Để thiết lập thành công mối liên hệ với người bản địa, trưởng nhóm dự định tặng một món quà cho thủ lĩnh của mỗi bộ lạc mà anh ta gặp. Để đạt được mục đích này, anh ấy đã mang theo một chuỗi thủy tinh dài, tương tự như đá quý.
Hãy biểu diễn chuỗi dưới dạng chuỗi s, bao gồm các chữ cái nhỏ trong bảng chữ cái tiếng Anh, trong đó mỗi chữ cái có nghĩa là loại mảnh thủy tinh ở vị trí tương ứng.
Các nhà nghiên cứu sẽ cắt chuỗi thành một số mảnh, sau đó giao chính xác một mảnh cho thủ lĩnh của mỗi bộ lạc mà nhóm gặp phải. Trưởng nhóm nghiên cứu đã quyết định chia chuỗi thành các đoạn theo các quy tắc sau:

Để không mất nhiều thời gian cho việc cắt, mỗi mảnh phải là một nhóm các mảnh thủy tinh liền kề trong chuỗi, tức là một chuỗi con của chuỗi s.
Tất cả các mảnh thủy tinh phải được sử dụng, nghĩa là mỗi mảnh thủy tinh phải được bao gồm trong đúng một mảnh.
Bởi vì các nhà nghiên cứu không biết thổ dân đánh giá một số loại thủy tinh như thế nào nên họ muốn mỗi tù trưởng nhận được cùng một bộ thủy tinh mà không quan tâm đến thứ tự. Nói cách khác, đối với bất kỳ loại thủy tinh nào thì số lượng thủy tinh loại này trong mỗi mảnh vỡ phải bằng nhau.
Các nhà nghiên cứu không biết có bao nhiêu bộ lạc sống trên đảo, vì vậy số lượng mảnh vỡ được chuẩn bị phải càng nhiều càng tốt.

Giúp người quản lý xác định số mảnh tối đa có thể thu được.

Đầu vào:
Dòng đầu tiên chứa chuỗi s (1 <= |s| <= 5000000).

Đầu ra:
In một số duy nhất - số lượng mảnh tối đa có thể mà các nhà nghiên cứu có thể cắt chuỗi mà họ có mà không vi phạm bất kỳ điều kiện nào do trưởng nhóm đặt ra.

Ví dụ:

Giải thích:
Trong ví dụ đầu tiên, các nhà nghiên cứu có thể phá vỡ chuỗi 'abbabbbab' mảnh 'abb', 'abb', 'bab' thì thủ lĩnh của mỗi bộ tộc họ gặp sẽ nhận được một ly loại 'a' và hai mảnh 'b'.

Trong ví dụ thứ hai, chuỗi không thể được chia thành nhiều hơn một đoạn của chuỗi, tuân theo tất cả các điều kiện.

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