هش کردن

Error

به جای اینکه فقط هش یک دنباله را محاسبه کنیم، می توانیم مقدار را در هر یک از پیشوندهای آن ذخیره کنیم. توجه داشته باشید که اینها مقادیر هش برای دنباله هایی برابر با پیشوند مربوطه خواهند بود.

با چنین ساختاری، می توانید به سرعت مقدار هش را برای هر زیربخشی از این دنباله (شبیه به جمع پیشوندها) محاسبه کنید.

اگر بخواهیم هش زیربخش [l;r] را محاسبه کنیم، باید هش پیشوند r را بگیریم و هش پیشوند l-1 را در p ضرب کنیم به توان r-l+1. اگر این مقادیر را روی پیشوندها بنویسید و ببینید چه اتفاقی می‌افتد، دلیل این امر مشخص می‌شود. امیدوارم با دیدن این عکس موفق باشید.



در نتیجه چنین اقداماتی، یک هش از یک زیربخش از دنباله اصلی دریافت می کنیم. علاوه بر این، این هش برابر با آن است که به عنوان هش از دنباله ای برابر با این زیربخش در نظر گرفته شود (برای مقایسه با مقادیر دیگر نیازی به تبدیل اضافی درجه یا موارد مشابه نیست).

در اینجا دو نکته قابل توضیح است:
1) برای ضرب سریع p در توان r-l+1، لازم است تمام توان های ممکن مدول p modulo از قبل محاسبه شود.
2) باید به خاطر داشت که ما همه محاسبات مدول مدول را انجام می دهیم و بنابراین ممکن است معلوم شود که پس از کم کردن هش های پیشوند، یک عدد منفی به دست می آوریم. برای جلوگیری از این امر، همیشه می‌توانید مد را قبل از تفریق اضافه کنید. همچنین فراموش نکنید که مقدار مدول را بعد از ضرب و همه جمع ها بگیرید.

در کد به صورت زیر است:
  #include <bits/stdc++.h> با استفاده از namespace std. typedef long longll; const int MAXN = 1000003; // ماژول پایه و هش ll p، mod; // پیشوند هش و توان p h[MAXN]، pows[MAXN]؛ // محاسبه هش زیربخش [l;r] ll get_segment_hash(int l, int r) { بازگشت (h[r] + mod - h[l - 1] * pows[r - l + 1] % mod) % mod; } int main() { // به نوعی p و mod را دریافت کنید // پیش محاسبه توان ها ص pows[0] = 1; برای (int i = 0; i < MAXN; i++) pows[i] = (pows[i - 1] * p) % mod; // // راه حل اصلی مشکل // بازگشت 0; }

اگر هش رشته A برابر با h_A و هش رشته B برابر با h_B داشته باشیم، می‌توانیم به سرعت هش رشته AB را محاسبه کنیم:
h_AB = h_A * p^|B| + h_B   <- شمارش همه چیز مدولو
کجا |B| - طول رشته B.

علاوه بر دنباله ها، می توانید مجموعه ها را نیز هش کنید. یعنی مجموعه ای از اشیاء بدون نظم بر روی آنها. طبق فرمول زیر محاسبه می شود:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- شمارش همه چیز مدولو
که در آن ord تابعی است که به یک شی از مجموعه، عدد ترتیبی مطلق خود را در بین تمام اشیاء ممکن نسبت می دهد (مثلاً اگر اشیاء اعداد طبیعی باشند، ord(x) = x، و اگر حروف لاتین کوچک باشد، ord(& #39;a') = 1، ord('b') = 2 و غیره)

یعنی برای هر شی مقداری برابر با پایه به توان تعداد این شیء مرتبط می کنیم و همه این مقادیر را جمع می کنیم تا یک هش از کل مجموعه به دست آوریم. همانطور که از فرمول مشخص است، اگر عنصری به مجموعه اضافه یا از آن حذف شود، هش به راحتی دوباره محاسبه می شود (فقط مقدار مورد نیاز را اضافه یا کم کنید). همین منطق،  اگر عناصر منفرد اضافه یا حذف نشوند، بلکه مجموعه های دیگر (فقط هش آنها را اضافه یا کم کنید).

همانطور که قبلاً می توانید درک کنید، عناصر منفرد به عنوان مجموعه هایی با اندازه 1 در نظر گرفته می شوند که می توانیم هش را برای آنها محاسبه کنیم. و مجموعه های بزرگتر به سادگی ترکیبی از چنین مجموعه های منفردی هستند که با ترکیب مجموعه ها، هش آنها را اضافه می کنیم.

در واقع، این هنوز همان هش چند جمله ای است، اما قبل از ضریب p^m ، مقدار را داشتیم. از عنصر دنباله زیر عدد n - m - 1 (که در آن n طول دنباله است) و اکنون این تعداد عناصر مجموعه است که عدد ترتیبی مطلق آنها برابر با m است.

در چنین هش‌سازی، باید یک پایه به اندازه کافی بزرگ (بزرگتر از حداکثر اندازه مجموعه) انتخاب کرد یا از هش مضاعف استفاده کرد تا از موقعیت‌هایی اجتناب شود که مجموعه‌ای از اشیاء p با عدد ترتیبی مطلق m دارای هش یکسانی با مجموعه‌ای با یک شی با مطلق باشد. عدد ترتیبی m+1.
 

همچنین چندین راه برای هش کارآمد درختان ریشه دار وجود دارد. 
یکی از این روش ها به صورت زیر مرتب شده است:
ما رئوس را به صورت بازگشتی و به ترتیب پیمایش در عمق پردازش می کنیم. فرض می کنیم که هش یک راس منفرد برابر با p باشد. برای رئوس با فرزندان، ابتدا الگوریتم را برای آنها اجرا می کنیم، سپس از طریق فرزندان، هش زیردرخت فعلی را محاسبه می کنیم. برای این کار هش های زیردرخت های کودکان را به صورت دنباله ای از اعداد در نظر بگیرید و هش را از روی این دنباله محاسبه کنید. این هش زیردرخت فعلی خواهد بود.
اگر ترتیب روی فرزندان برای ما مهم نیست، قبل از محاسبه هش، دنباله هش ها را از زیردرخت های فرزند مرتب می کنیم و سپس هش را از دنباله مرتب شده محاسبه می کنیم.

به این ترتیب می توانید هم شکلی درختان را بررسی کنید - فقط هش را بدون ترتیب روی بچه ها بشمارید (یعنی هر بار هش های بچه ها را مرتب کنید). و اگر هش های ریشه ها مطابقت داشته باشند، درخت ها هم شکل هستند، در غیر این صورت نه.

برای درختان بدون ریشه، همه چیز به روشی مشابه اتفاق می افتد، اما مرکز باید به عنوان ریشه در نظر گرفته شود. یا اگر دو مرکز وجود دارد یک جفت هش در نظر بگیرید.