تجزئة السلاسل متعددة الحدود
مقارنة السلاسل الفرعية في زمن ثابت
تجزئة السلاسل متعددة الحدود درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 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)، والحماية من التصادمات. 🚀
تعلم Coding Interview Prep مع معلم ذكاء اصطناعي — مجانًا
اكتب وقم بتشغيل أكوادك الفعلية في المتصفح، واحصل على مساعدة فورية من معلم ذكاء اصطناعي متاح 24/7، واستمر من حيث توقفت على الويب أو في التطبيق.
- الدورات
- 90
- الدروس
- 360
الأسئلة الشائعة
هل درس «تجزئة السلاسل متعددة الحدود» مجاني؟
نعم — نص درس «تجزئة السلاسل متعددة الحدود» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «تجزئة السلاسل متعددة الحدود»؟
مقارنة السلاسل الفرعية في زمن ثابت تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «تجزئة السلاسل متعددة الحدود»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- دالة بادئة KMP
- تجزئة السلاسل متعددة الحدود
- دالة Z للبحث عن الأنماط
- أشجار Trie للبحث عن البادئات