Courses

Algoritma

Hashing

Module: Hashing

Problem

7 /8

hubungan budaya

Theory Click to read/hide

Selain jujukan, anda juga boleh set cincang. Iaitu, set objek tanpa susunan padanya. Ia dikira mengikut formula berikut:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\) <- mengira semua modulo
di mana ord ialah fungsi yang menetapkan kepada objek bagi set nombor ordinal mutlaknya di antara semua objek yang mungkin (contohnya, jika objek adalah nombor asli, maka ord(x) = x, dan jika huruf Latin huruf kecil, maka ord(& #39;a' ;) = 1, ord('b') = 2 dsb.)

Iaitu, untuk setiap objek kita mengaitkan nilai yang sama dengan asas dengan kuasa nombor objek ini dan merumuskan semua nilai ini untuk mendapatkan cincangan keseluruhan set. Seperti yang jelas daripada formula, cincang mudah dikira semula jika elemen ditambah atau dialih keluar daripada set (hanya tambah atau tolak nilai yang diperlukan). Logik yang sama, jika tidak satu elemen ditambah atau dialih keluar, tetapi set lain (hanya tambah / tolak cincangnya).

Seperti yang anda sudah faham, elemen tunggal dianggap sebagai set saiz 1, yang mana kita boleh mengira cincangan. Dan set yang lebih besar hanyalah gabungan set tunggal tersebut, di mana dengan menggabungkan set, kami menambah cincangnya.

Sebenarnya, ini masih cincang polinomial yang sama, tetapi sebelum pekali pada p^m , kami mempunyai nilai daripada unsur jujukan di bawah nombor n - m - 1 (dengan n ialah panjang jujukan), dan kini ini ialah bilangan unsur dalam set yang nombor ordinal mutlaknya adalah sama dengan m.

Dalam pencincangan sedemikian, seseorang mesti mengambil tapak yang cukup besar (lebih besar daripada saiz set maksimum), atau menggunakan pencincangan berganda untuk mengelakkan situasi di mana set objek p dengan nombor ordinal mutlak m mempunyai cincangan yang sama seperti set dengan satu objek dengan mutlak nombor ordinal m+1.

Problem

Pada awal abad ke-18, sekumpulan penjelajah Eropah tiba di sebuah pulau yang didiami oleh sekumpulan puak yang tidak pernah berhubung dengan wakil tamadun Eropah.

Untuk berjaya menjalinkan hubungan dengan orang asli, ketua kumpulan itu merancang untuk memberi hadiah kepada ketua setiap suku yang ditemuinya. Untuk tujuan ini, dia membawa rantai kaca yang panjang, serupa dengan batu permata.
Mari kita wakili rentetan sebagai rentetan s, yang terdiri daripada huruf kecil abjad Inggeris, di mana setiap huruf bermaksud jenis kepingan kaca pada kedudukan yang sepadan.
Para penyelidik akan memotong rantai itu kepada beberapa serpihan, dan kemudian menyerahkan tepat satu serpihan kepada ketua setiap suku yang ditemui oleh kumpulan itu. Ketua penyelidikan memutuskan untuk membahagikan rantai kepada serpihan mengikut peraturan berikut:

Untuk tidak menghabiskan banyak masa untuk memotong, setiap serpihan hendaklah sekumpulan kepingan kaca bersebelahan dalam rantai, iaitu subrentetan rentetan s.
Semua kepingan kaca mesti digunakan, iaitu setiap kepingan kaca mesti disertakan dalam satu serpihan.
Oleh kerana penyelidik tidak tahu bagaimana orang asli akan menghargai jenis kaca tertentu, mereka mahu setiap ketua mendapatkan set kaca yang sama tanpa mengira pesanan. Dalam erti kata lain, untuk sebarang jenis kaca, bilangan kaca jenis ini mestilah sama dalam setiap serpihan.
Penyelidik tidak tahu berapa banyak suku yang tinggal di pulau itu, jadi bilangan serpihan yang disediakan haruslah sebanyak mungkin.

Bantu pengurus menentukan bilangan maksimum serpihan yang boleh diperolehi.

Input:
Baris pertama mengandungi rentetan s (1 <= |s| <= 5000000).

Output:
Cetak satu nombor - bilangan maksimum serpihan yang mungkin di mana penyelidik boleh memotong rantai yang mereka miliki tanpa melanggar mana-mana syarat yang dirumuskan oleh ketua kumpulan.

Contoh:

Penjelasan:
Dalam contoh pertama, penyelidik boleh memutuskan rantaian 'abbabbbab' serpihan 'abb', 'abb', 'bab', maka ketua setiap puak yang mereka temui akan mendapat satu gelas jenis 'a' dan dua keping 'b'.

Dalam contoh kedua, rentetan tidak boleh dibahagikan kepada lebih daripada satu serpihan rantai, memerhatikan semua keadaan.

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