دالة البادئة KMP

الخطوة 1: فهم دالة البادئة (Prefix Function). دالة البادئة π[i] للـ pattern هي أقصى طول لأطول بادئة صحيحة للـ pattern تنتهي عند index i بحيث تكون مساوية للـ suffix المنتهي عند i. بمعنى آخر، π[i] = أطول طول k < i+1 بحيث pattern[0:k] == pattern[i-k+1:i+1]. تستخدم هذه الدالة في خوارزمية KMP لتحديد مدى التقدم عندما يحدث عدم تطابق.

الخطوة 2: إدخال النمط (Pattern) في الحقل المخصص. على سبيل المثال، أدخل النمط 'ababaca'. سيقوم الحاسب بحساب دالة البادئة لكل حرف من الـ pattern.

الخطوة 3: عملية الحساب. تبدأ الخوارزمية بتهيئة π[0]=0. ثم لكل حرف i من 1 إلى n-1، نستخدم قيمة π السابقة لتحديد أين نبدأ المقارنة. نأخذ k=π[i-1]. إذا كان pattern[k]==pattern[i]، نزيد k (π[i]=k+1). وإلا، إذا كان k>0، نعدل k=π[k-1] ونعيد المقارنة. نكرر حتى نحصل على تطابق أو k=0.