تجزئة السلاسل متعددة الحدود
مقارنة السلاسل الفرعية في زمن ثابت
تجزئة السلاسل متعددة الحدود درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
مقارنة السلاسل الفرعية بسرعة
غالبًا ما تحتاج إلى معرفة ما إذا كانت سلسلتان فرعيتان متساويتين. فالفحص محرفًا بمحرف بطيء، لذا نحوّل كل سلسلة إلى رقم. 🔢
فكرة التجزئة
تربط التجزئة سلسلةً نصية بعدد صحيح واحد. وإذا اختلفت سلسلتان، فغالبًا ما تختلف قيمتا التجزئة أيضًا.
عامِل السلاسل كمتعددات حدود
نقرأ كل محرف باعتباره رقمًا في أساس p. ويحوّل هذا المنظور متعدد الحدود السلسلة إلى مجموع موزون كبير واحد.
h = ord(s[0]) + ord(s[1]) * p + ord(s[2]) * p * pاختر أساسًا ومعاملًا
اختر أساسًا أوليًا مثل 31، ومعاملًا أوليًا كبيرًا. ويحافظ المعامل على صغر الأعداد ويمنع تجاوز السعة.
BASE = 31
MOD = 10**9 + 9حساب تجزئة واحدة
مرّر على السلسلة وادمج كل محرف باستخدام قاعدة Horner، مع أخذ باقي القسمة على المعامل في كل خطوة.
h = 0
for c in s:
h = (h * BASE + ord(c)) % MODتجزئات البادئات
خزّن تجزئة بادئة لكل موضع. عندها يمكن حساب تجزئة أي سلسلة فرعية بطرح سريع.
pre[i + 1] = (pre[i] * BASE + ord(s[i])) % MODقوى الأساس
عليك أيضًا حساب قوى الأساس مسبقًا. فهي تحاذي البادئتين عند إجراء الطرح.
pw[i] = (pw[i - 1] * BASE) % MODتجزئة سلسلة فرعية في O(1)
تجزئة s[l..r] هي طرح تجزئتي بادئتين، بعد تحجيم إحداهما بقوة من قوى الأساس. يستغرق كل استعلام زمنًا ثابتًا.
def sub(l, r):
return (pre[r] - pre[l] * pw[r - l]) % MODاحذروا من التصادمات
قد تتشارك سلسلتان مختلفتان في قيمة تجزئة واحدة؛ وهذا هو التصادم. وهو نادر الحدوث، لكن مسائل المسابقات قد تصمم أحيانًا مدخلات تؤدي إلى حدوثه.
التجزئة المزدوجة لمزيد من الأمان
استخدموا معاملين مستقلين، وقارنوا قيمتي التجزئة معًا. فمن المستبعد عمليًا حدوث تصادم في القيمتين في الوقت نفسه.
متى تتألق التجزئة
تتيح التجزئة مقارنة السلاسل الفرعية، والعثور على التكرارات، والبحث عن الأنماط. إنها أداة مرنة متعددة الاستخدامات.
تحقق سريع
اختاروا الأداة المناسبة لمقارنة عدد كبير من السلاسل الفرعية بأمان.
مراجعة: قوة التجزئة
يمكنكم الآن تحويل السلاسل إلى تجزئات متعددة الحدود، والاستعلام عن أي سلسلة فرعية في O(1)، والحماية من التصادمات. 🚀
الأسئلة الشائعة
هل درس «تجزئة السلاسل متعددة الحدود» مجاني؟
نعم — نص درس «تجزئة السلاسل متعددة الحدود» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «تجزئة السلاسل متعددة الحدود»؟
مقارنة السلاسل الفرعية في زمن ثابت تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «تجزئة السلاسل متعددة الحدود»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- دالة بادئة KMP
- تجزئة السلاسل متعددة الحدود
- دالة Z للبحث عن الأنماط
- أشجار Trie للبحث عن البادئات