تجزئة

Error

بدلاً من مجرد حساب تجزئة التسلسل ، يمكننا تخزين القيمة في كل بادئة. لاحظ أن هذه ستكون قيم تجزئة للتسلسلات التي تساوي البادئة المقابلة.

باستخدام مثل هذه البنية ، يمكنك حساب قيمة التجزئة بسرعة لأي جزء فرعي من هذا التسلسل (على غرار مجاميع البادئة).

إذا أردنا حساب تجزئة القطعة الفرعية [l ؛ r] ، فسنحتاج إلى أخذ التجزئة على البادئة r وطرح التجزئة على البادئة l-1 مضروبًا في p إلى قوة r-l + 1. لماذا يصبح هذا واضحًا إذا كتبت القيم على البادئات وشاهدت ما يحدث. أتمنى أن تنجح في النظر إلى هذه الصورة.



نتيجة لمثل هذه الإجراءات ، نحصل على تجزئة لجزء فرعي من التسلسل الأصلي. علاوة على ذلك ، فإن هذه التجزئة تساوي ذلك إذا تم اعتبارها تجزئة من تسلسل مساوٍ لهذه القطعة الفرعية (لا يلزم إجراء تحويلات إضافية للدرجات أو ما شابهها للمقارنة مع القيم الأخرى).

هناك نقطتان يجب توضيحهما هنا:
1) للمضاعفة بسرعة في p إلى القوة r-l + 1 ، من الضروري إجراء حساب مسبق لجميع القوى الممكنة لـ p modulo mod.
2) يجب أن نتذكر أننا نجري جميع العمليات الحسابية modulo modulo ، وبالتالي قد يتضح أنه بعد طرح تجزئات البادئة ، سنحصل على رقم سالب. لتجنب ذلك ، يمكنك دائمًا إضافة mod قبل الطرح. أيضا ، لا تنس أن تأخذ قيمة modulo بعد الضرب وكل الإضافات.

في الكود يبدو كالتالي:
نبسب ؛ # تضمين & lt؛ bits / stdc ++. h & gt؛ استخدام اسم للمحطة؛ typedef longll ؛ const int MAXN = 1000003 ؛ // قاعدة ووحدة تجزئة ليرة لبنانية ، وزارة الدفاع ؛ // بادئة التجزئة والأس ص 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 ؛ } انت مين() { // بطريقة ما الحصول على p و mod // حساب القوى المسبق ص أقواس [0] = 1 ؛ لـ (int i = 0؛ i & lt؛ MAXN؛ i ++) pows [i] = (pows [i - 1] * p)٪ mod ؛ // // حل المشكلة الرئيسية // العودة 0 ؛ }

إذا كان لدينا تجزئة السلسلة A تساوي h _A & nbsp ؛ وتجزئة السلسلة B تساوي h _B ، فيمكننا حساب تجزئة السلسلة AB بسرعة:
h _AB & nbsp؛ = h _A & nbsp؛ * p ^{| B |} & nbsp؛ + h _B & nbsp؛ على & nbsp ؛ العلامة & lt ؛ - عد كل شيء modulo
حيث | ب | - طول الخيط ب.

بالإضافة إلى التسلسلات ، يمكنك أيضًا تجزئة المجموعات. أي ، مجموعات من الأشياء بدون ترتيب عليها. يتم حسابه وفقًا للصيغة التالية:
hash (A) = & nbsp؛ \ (\ sum_ {a \ in A} p ^ {ord (a)} \) & nbsp؛ على & nbsp ؛ العلامة & lt ؛ - عد كل شيء modulo
حيث ord هي وظيفة تُسند إلى كائن من المجموعة رقمها الترتيبي المطلق بين جميع الكائنات الممكنة (على سبيل المثال ، إذا كانت الكائنات أرقامًا طبيعية ، فعندها ord (x) = x ، وإذا كانت الأحرف اللاتينية صغيرة ، ثم ord (& # 39 ؛ a & # 39 ؛) = 1 ، أمر (& # 39 ؛ ب & # 39 ؛) = 2 وما إلى ذلك)

أي ، لكل كائن ، نربط قيمة مساوية للقاعدة بقوة رقم هذا الكائن ونلخص كل هذه القيم من أجل الحصول على تجزئة للمجموعة بأكملها. كما هو واضح من الصيغة ، يمكن إعادة حساب التجزئة بسهولة إذا تمت إضافة عنصر إلى المجموعة أو إزالتها منها (فقط قم بإضافة أو طرح القيمة المطلوبة). نفس المنطق ، & nbsp؛ إذا لم تتم إضافة عناصر مفردة أو إزالتها ، ولكن هناك مجموعات أخرى (فقط قم بإضافة / طرح التجزئة الخاصة بهم).

كما يمكنك أن تفهم بالفعل ، تعتبر العناصر الفردية مجموعات من الحجم 1 ، والتي يمكننا حساب التجزئة لها. والمجموعات الأكبر هي ببساطة اتحاد لمثل هذه المجموعات المفردة ، حيث من خلال دمج المجموعات ، نضيف تجزئاتها.

في الواقع ، لا يزال هذا هو نفس تجزئة متعدد الحدود ، ولكن قبل المعامل عند p ^m & nbsp ؛، كان لدينا القيمة لعنصر التسلسل تحت الرقم n - m - 1 (حيث n هو طول التسلسل) ، والآن هذا هو عدد العناصر في المجموعة التي يساوي عددها الترتيبي المطلق م.

في مثل هذا التجزئة ، يجب على المرء أن يأخذ قاعدة كبيرة بما فيه الكفاية (أكبر من الحد الأقصى لحجم المجموعة) ، أو يستخدم التجزئة المزدوجة لتجنب المواقف التي يكون فيها لمجموعة من الكائنات p ذات العدد الترتيبي المطلق m نفس التجزئة كمجموعة مع كائن واحد مع مطلق عدد ترتيبي م + 1.
نبسب ؛

هناك أيضًا عدة طرق لتجزئة الأشجار ذات الجذور بكفاءة. & nbsp؛
إحدى هذه الطرق مرتبة على النحو التالي:
نقوم بمعالجة الرؤوس بشكل متكرر ، بترتيب الاجتياز في العمق. سنفترض أن تجزئة رأس واحد تساوي p. للرؤوس مع الأطفال ، نقوم أولاً بتشغيل الخوارزمية لهم ، ثم من خلال الأطفال سنحسب تجزئة الشجرة الفرعية الحالية. للقيام بذلك ، ضع في اعتبارك تجزئة الأشجار الفرعية للأطفال كسلسلة من الأرقام وحساب التجزئة من هذا التسلسل. سيكون هذا هو تجزئة الشجرة الفرعية الحالية.
إذا لم يكن الترتيب على الأطفال مهمًا بالنسبة لنا ، فقبل حساب التجزئة ، نقوم بفرز تسلسل التجزئة من الأشجار الفرعية الفرعية ثم حساب التجزئة من التسلسل المصنف.

بهذه الطريقة يمكنك التحقق من تماثل الأشجار - ما عليك سوى حساب التجزئة بدون ترتيب على الأطفال (أي في كل مرة تقوم بفرز تجزئة الأطفال). وإذا كانت تجزئات الجذور متطابقة ، فإن الأشجار تكون متشابهة ، وإلا لا.

بالنسبة للأشجار غير المقطوعة ، يحدث كل شيء بطريقة مماثلة ، ولكن يجب اعتبار النقطه الوسطى هي الجذر. أو ضع في اعتبارك زوجًا من التجزئة إذا كان هناك نقطتان.