TechCodeview

يقدم نوث موريس وبرات خوارزمية زمنية خطية لمشكلة مطابقة السلسلة. يتم تحقيق وقت المطابقة لـ O (n) عن طريق تجنب المقارنة مع عنصر 'S' الذي سبق أن تم تضمينه في المقارنة مع بعض عناصر النموذج 'p' المراد مطابقته. أي أن التراجع عن السلسلة 'S' لا يحدث أبدًا

مكونات خوارزمية KMP:

1. وظيفة البادئة (Π): تقوم وظيفة البادئة Π للنمط بتغليف المعرفة حول كيفية تطابق النمط مع التحول نفسه. يمكن استخدام هذه المعلومات لتجنب التحول غير المجدي للنمط 'p'. بمعنى آخر، يتيح ذلك تجنب التراجع عن السلسلة 'S'.

2. مباريات KMP: باستخدام السلسلة 'S' والنمط 'p' ووظيفة البادئة 'Π' كمدخلات، ابحث عن حدوث 'p' في 'S' وقم بإرجاع عدد تحولات 'p' التي تم العثور على التكرارات بعدها.

وظيفة البادئة (Π)

بعد الكود الزائف حساب وظيفة البادئة، Π:

 <strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m &#x2190;length [P] //&apos;p&apos; pattern to be matched 2. &#x3A0; [1] &#x2190; 0 3. k &#x2190; 0 4. for q &#x2190; 2 to m 5. do while k &gt; 0 and P [k + 1] &#x2260; P [q] 6. do k &#x2190; &#x3A0; [k] 7. If P [k + 1] = P [q] 8. then k&#x2190; k + 1 9. &#x3A0; [q] &#x2190; k 10. Return &#x3A0; 

تحليل وقت التشغيل:

في الكود الزائف أعلاه لحساب وظيفة البادئة، يتم تشغيل حلقة for من الخطوة 4 إلى الخطوة 10 مرات 'm'. تستغرق الخطوة 1 إلى الخطوة 3 وقتًا ثابتًا. ومن ثم فإن وقت تشغيل وظيفة البادئة الحسابية هو O (m).

مثال: احسب Π للنمط 'p' أدناه:

ماذا يعني xd

حل:

 Initially: m = length [p] = 7 Π [1] = 0 k = 0 

بعد التكرار 6 مرات، اكتمل حساب دالة البادئة:

يطابق KMP:

يعثر KMP Matcher مع النمط 'p' والسلسلة 'S' ووظيفة البادئة 'Π' كمدخل، على تطابق p في S. باتباع التعليمات البرمجية الزائفة، قم بحساب المكون المطابق لخوارزمية KMP:

 <strong>KMP-MATCHER (T, P)</strong> 1. n &#x2190; length [T] 2. m &#x2190; length [P] 3. &#x3A0;&#x2190; COMPUTE-PREFIX-FUNCTION (P) 4. q &#x2190; 0 // numbers of characters matched 5. for i &#x2190; 1 to n // scan S from left to right 6. do while q &gt; 0 and P [q + 1] &#x2260; T [i] 7. do q &#x2190; &#x3A0; [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q &#x2190; q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print &apos;Pattern occurs with shift&apos; i - m 12. q &#x2190; &#x3A0; [q] // look for the next match 

تحليل وقت التشغيل:

يتم تشغيل حلقة for التي تبدأ في الخطوة 5 مرات 'n'، أي ما دام طول السلسلة 'S'. نظرًا لأن الخطوات من 1 إلى الخطوة 4 تستغرق أوقاتًا ثابتة، فإن وقت التشغيل يهيمن عليه هذا بالنسبة للحلقة. وبالتالي فإن وقت تشغيل وظيفة المطابقة هو O (n).

مثال: إعطاء سلسلة 'T' ونمط 'P' كما يلي:

دعونا ننفذ خوارزمية KMP لمعرفة ما إذا كان 'P' يحدث في 'T'.

بالنسبة لـ 'p' وظيفة البادئة، ؟ تم حسابها سابقا وهي كالتالي:

حل:

 Initially: n = size of T = 15 m = size of P = 7 

تم العثور على النمط 'P' ليحدث تعقيدًا في السلسلة 'T.' إجمالي عدد التحولات التي حدثت حتى يتم العثور على التطابق هو i-m = 13 - 7 = 6 تحولات.