لحل هذه المشكلة ، لن يعمل التعداد المعتاد ، لأن ستكون مقارباتها O (t * s). لذلك ، لمهام البحث عن السلاسل الفرعية ، يتم استخدام خوارزمية KMP (Knuth-Morris-Pratt).
لتنفيذ هذه الخوارزمية ، يتم استخدام دالة بادئة السلسلة ، وهي عبارة عن مصفوفة من أرقام الطول n & nbsp؛ (strong> s length) ، حيث يكون كل عنصر هو الحد الأقصى للطول من أكبر اللاحقة الخاصة بالسلسلة الفرعية s ، على & nbsp ؛ تطابق البادئة الخاصة بها. على سبيل المثال:
نبسب ؛
<الجسم>
| خط
| وظيفة البادئة
| ملاحظة
|
| abababcab |
0 0 1 2 3 & nbsp؛ 4 & nbsp؛ 0 1 2 |
& nbsp؛ |
| abcabcd |
0 0 0 1 2 3 0 |
& nbsp؛ |
| aabaaab |
0 1 0 1 2 2 3 |
& nbsp؛ |
خوارزمية دالة بادئة تافهة مع O (n ^ 3) مقاربة:
المتجه & lt؛ int & gt؛ prefix_function (string s) {
int n = ( int ) طول () ؛
المتجه & lt؛ int & gt؛ بي (ن) ؛
لـ ( int i = 0 ؛ i & lt؛ n؛ ++ i)
لـ ( int k = 0 ؛ k & lt؛ = i؛ ++ k)
if (s.substr ( 0 ، k) == s .substr (i - ك + 1 ، k))
pi [i] = k؛
عودة بي ؛
}
والآن نحتاج إلى إنشاء وظيفة بادئة لسلسلة من الشكل: & nbsp؛
t + # +
s ، حيث # هو حرف محدد من الواضح أنه غير موجود في النص. & nbsp؛ عند تحليل قيم دالة البادئة بعد الحرف الفاصل المقابل ، تجدر الإشارة إلى أنه إذا كانت القيمة الناتجة مساوية لطول السلسلة الفرعية المطلوبة ، فسيتم العثور على حدوثها. على سبيل المثال ، للسلسلة & quot؛ abababcab & quot؛ والسلسلة الفرعية المرغوبة & quot؛ abab & quot؛ ، ستكون وظيفة البادئة:
0 0 1 2 0 1 2 3 4 3 4 0 1 2 نحتاج إلى تحليل عناصر السلسلة المقابلة s:
1 2 3 4 3 4 0 1 2 - هناك حالتان حيث تكون القيمة 4 (الرابع والسادس) ، أي طول
t ، & nbsp؛ نتيجة لذلك ، يجب كتابة الإجابة: 4 - 4 (طول t) & nbsp؛ = 0 و 6 - 4 = 2. يمكن ملاحظة أن هذه هي الإجابات الصحيحة والسلسلة & quot؛ abab & quot؛ هي في الواقع سلسلة فرعية في السلسلة & quot؛ abababcab & quot؛ في المواضع 0 و 2.
نبسب ؛