بدلاً من مجرد حساب تجزئة التسلسل ، يمكننا تخزين القيمة في كل بادئة. لاحظ أن هذه ستكون قيم تجزئة للتسلسلات التي تساوي البادئة المقابلة.
باستخدام مثل هذه البنية ، يمكنك حساب قيمة التجزئة بسرعة لأي جزء فرعي من هذا التسلسل (على غرار مجاميع البادئة).
إذا أردنا حساب تجزئة القطعة الفرعية [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 ؛
}