وظيفة البادئة ، وظيفة Z.


لحل هذه المشكلة ، لن يعمل التعداد المعتاد ، لأن ستكون مقارباتها 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.

نبسب ؛

Training problem

(C ++) بحث سلسلة فرعية ، KMP ، متغير تافه: ابدأ

بعد تحسين وظيفة البادئة (للحصول على تفاصيل هنا ) ، نحصل على الخوارزمية النهائية باستخدام O (n) المقاربات: 

المتجه  & lt؛   int   & gt؛  prefix_function (string s) {
 int  n  =  ( int  ) طول () ؛
المتجه  & lt؛   int   & gt؛  بي (ن) ؛
 لـ  ( int  i  = 1 ؛ i  & lt؛  n؛  ++  i) {
 int  j  =  pi [i  - 1 < / span>]؛
 while  (j  & gt؛   0   & amp؛ & amp؛  s [i] ! =  s [j])
j  =  pi [j  - 1 ]؛
 if  (s [i]  ==  s [j])  ++  ي ؛
pi [i]  =  j؛
}
 عودة  بي ؛
}

Training problem

وظيفة البادئة

Z وظيفة
Z -الوظيفة من السلسلة S - المصفوفة Z ، كل عنصر منها هو Z [i] يساوي أطول بادئة في السلسلة الفرعية التي تبدأ من الموضع i في السلسلة S ، وهي أيضًا بادئة السلسلة Z . قيمة الدالة Z في الموضع صفر عادةً ما تكون إما صفرًا أو طول السلسلة بأكملها.
صعوبة
O (| S | ^ 2) أو O (| S |) .
& nbsp؛
دالة بادئة من السلسلة S - صفيف P ، كل عنصر منها P [i] يساوي أطول لاحقة في تبدأ السلسلة الفرعية من الموضع i في السلسلة S ، وهي أيضًا لاحقة السلسلة بأكملها S . قيمة الدالة P - عند الموضع صفر هي إما صفر أو طول السلسلة بأكملها. & nbsp؛
صعوبة
O (| S | ^ 2) أو O (| S |) .
& nbsp؛
حاول تنفيذ دالة Z و وظيفة البادئة & nbsp؛ لـ O (| S | ^ 2) .

Training problem

وظيفة Z

& nbsp؛
يمكن استخدام كل من Z وبادئة الوظيفة لتنفيذ خوارزمية KMP (Knuth-Morris-Pratt) للعثور على سلسلة فرعية في سلسلة في O (| S |). جوهر هذه الخوارزمية هو كما يلي: ننسب إلى السلسلة التي نريد إيجاد السلسلة التي نبحث فيها. من المستحسن للغاية وضع حرف فاصل بين هذه السطور ، أي حرف لا يظهر في أي سطر (عادة #).

Training problem

الشفرة