TechCodeview

Knuth-Moris ו-Pratt מציגים אלגוריתם זמן ליניארי לבעיית התאמת המיתרים. זמן התאמה של O (n) מושג על ידי הימנעות מהשוואה עם אלמנט של 'S' שהיו מעורבים בעבר בהשוואה לאלמנט כלשהו של התבנית 'p' שיש להתאים. כלומר, חזרה לאחור על המחרוזת 'S' לעולם לא מתרחשת

רכיבי אלגוריתם KMP:

1. פונקציית הקידומת (Π): פונקציית הקידומת, Π עבור דפוס מקפלת ידע על האופן שבו הדפוס מתאים לשינוי של עצמו. ניתן להשתמש במידע זה כדי למנוע שינוי חסר תועלת של התבנית 'עמ'. במילים אחרות, זה מאפשר הימנעות מחזרה לאחור של המחרוזת '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' למטה:

isletter java

פִּתָרוֹן:

 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 תורנויות.