دالة بادئة KMP
العثور على نمط في O(n + m)
دالة بادئة KMP درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 1 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
مشكلة مطابقة الأنماط
تريد العثور على موضع ظهور نمط صغير داخل نص كبير. الفحوص الساذجة بطيئة، لذا تكافئ مسابقات البرمجة المسح الأذكى. 🔍
لماذا يسبب البحث الساذج مشكلات
قد تستغرق مقارنة النمط في كل موضع زمنًا قدره O(n*m). ومع المدخلات الكبيرة، قد يتجاوز ذلك حد الوقت بهدوء.
تعرّف إلى دالة البادئة
تقيس دالة البادئة، عند كل موضع، طول أطول بادئة صحيحة تكون أيضًا لاحقة. وهي جوهر KMP.
البادئة واللاحقة الصحيحتان
البادئة أو اللاحقة الصحيحة لا تكون السلسلة كاملة. في ababa، يبلغ طول أطول زوج متطابق 3، وهو aba.
ما الذي تخزنه pi[i]
نخزّن القيم في مصفوفة تسمى pi. وهنا تمثل pi[i] طول أطول بادئة ولاحقة لذلك الجزء المنتهي عند الفهرس i.
بناء pi في مرور واحد
تبني pi من اليسار إلى اليمين، مع إعادة استخدام القيم السابقة بدلًا من إعادة الفحص من البداية. وإعادة الاستخدام هذه هي الحيلة كلها.
def prefix_function(s):
pi = [0] * len(s)
return piحلقة الرجوع
عند عدم تطابق المحارف، ارجع إلى pi[k-1] بدلًا من إعادة الضبط إلى الصفر. فهذا يتجنب تكرار العمل.
while k > 0 and s[i] != s[k]:
k = pi[k - 1]تمديد التطابق
إذا كانت المحارف الحالية متطابقة، فزد الطول بمقدار واحد وسجّله. أما حالات عدم التطابق عند الصفر فتبقى صفرًا.
if s[i] == s[k]:
k += 1
pi[i] = kالبحث باستخدام الحيلة
للبحث عن نمط داخل نص، ادمجهما بالشكل pattern + sep + text. وتشير أي قيمة pi تساوي طول النمط إلى تطابق كامل.
combined = pattern + chr(0) + text
pi = prefix_function(combined)لماذا يهم الفاصل
الفاصل هو رمز لا يظهر في أي من السلسلتين. ويمنع الفاصل التطابقات من التسرب عبر موضع الدمج والتسبب في نتائج خاطئة.
مكسب الزمن الخطي
يعمل كل من البناء والبحث بتعقيد O(n + m). تتم معالجة كل محرف مرة واحدة، لذلك تتعامل KMP مع مدخلات المسابقات الضخمة بكفاءة.
تحقق سريع
اختبر مدى فهمك لما تسجله دالة البادئة.
مراجعة: KMP باختصار
لقد تعلمت دالة البادئة: ابنِ pi مرة واحدة، وارجع عند عدم التطابق، وابحث في زمن خطي. هذه هي KMP باختصار. 🎯
الأسئلة الشائعة
هل درس «دالة بادئة KMP» مجاني؟
نعم — نص درس «دالة بادئة KMP» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «دالة بادئة KMP»؟
العثور على نمط في O(n + m) تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 1 من أصل 4.
كم من الوقت يستغرق درس «دالة بادئة KMP»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.