دالة Z للبحث عن الأنماط
مطابقة البادئات عبر السلسلة
دالة Z للبحث عن الأنماط درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
أداة أخرى للمطابقة
تُعد دالة Z بديلًا واضحًا عن KMP للبحث عن الأنماط. ويجد كثيرون أن التفكير فيها أسهل. ✨
ماذا تعني z[i]
لكل فهرس، تمثل z[i] طول أطول سلسلة فرعية تبدأ عند i وتطابق بادئة السلسلة الكاملة أيضًا.
مثال صغير
بالنسبة إلى aabaab، تكون قيم z هي 0,1,0,3,1,0. عند الفهرس 3، تطابق السلسلة aab البادئة، ولذلك يكون طولها 3.
صندوق Z
نتتبع نافذة [l, r]، وهي أبعد تطابق إلى اليمين عثرنا عليه حتى الآن. ويسمح لنا ذلك بإعادة استخدام المقارنات السابقة.
l, r = 0, 0داخل الصندوق
عندما يقع i داخل الصندوق، انسخ قيمة z معروفة كبداية، على ألا تتجاوز طرف الصندوق.
if i < r:
z[i] = min(r - i, z[i - l])الامتداد بعد الصندوق
بعد الحصول على نقطة البداية، واصلوا مقارنة المحارف واحدًا تلو الآخر ما دامت تطابق البادئة.
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1تحريك الصندوق إلى الأمام
إذا امتد تطابقكم إلى موضع أبعد يمينًا، حدّثوا l وr حتى تتمكن الفهارس اللاحقة من إعادة استخدامه.
if i + z[i] > r:
l, r = i, i + z[i]ضمان الزمن الخطي
لا يتحرك الصندوق إلا إلى اليمين، لذا يكون إجمالي العمل O(n). ويسهم كل محرف بقدر محدود من العمل.
البحث باستخدام Z
ادمجوا pattern + sep + text ثم شغّلوا Z. كل قيمة z تساوي طول النمط تمثل تطابقًا.
combined = pattern + chr(0) + text
z = z_function(combined)استخراج التطابقات
افحصوا مصفوفة Z؛ فعندما تكون z[i] == len(pattern)، يبدأ التطابق عند الموضع المناظر في النص.
if z[i] == len(pattern):
matches.append(i - len(pattern) - 1)مقارنة Z وKMP
يعمل كل من Z وKMP في زمن خطي. وغالبًا ما تكون كتابة Z أبسط، لذا فهي بديل ممتاز ضمن أدواتكم.
تحقق سريع
تأكدوا من ترسخ معنى مصفوفة Z لديكم.
مراجعة: قوة دالة Z
أنشأتم مصفوفة Z باستخدام صندوق متحرك، وأجريتم البحث في زمن خطي، وأصبح لديكم الآن بديل واضح عن KMP. 🎯
الأسئلة الشائعة
هل درس «دالة Z للبحث عن الأنماط» مجاني؟
نعم — نص درس «دالة Z للبحث عن الأنماط» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «دالة Z للبحث عن الأنماط»؟
مطابقة البادئات عبر السلسلة تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «دالة Z للبحث عن الأنماط»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- دالة بادئة KMP
- تجزئة السلاسل متعددة الحدود
- دالة Z للبحث عن الأنماط
- أشجار Trie للبحث عن البادئات