אלגוריתם KMP

במדעי המחשב, אלגוריתם KMP הוא אלגוריתם להתאמת תבניות הפועל בזמן ליניארי במקרה הגרוע.
האלגוריתם התגלה בשנת 1970 על ידי דונלד קנות' ווואן פראת', ובאופן בלתי תלוי על ידי ג'יימס מוריס. השלושה פרסמו יחדיו את האלגוריתם בכתב העת SIAM בשנת 1977. 
מטרתו של האלגוריתם היא למצוא מופעים של מחרוזת P (תבנית, pattern) בתוך מחרוזת T (טקסט), כאשר .
בעוד האלגוריתם הנאיבי לביצוע פעולה זו פועל בזמן  בזמן הגרוע, אלגוריתם KMP עובד בזמן  בזמן גרוע.

תיאור האלגוריתם

נניח  וגם 
האלגוריתם הנאיבי להתאמת מחרוזות, יחפש עבור כל מיקום בטקסט האם הוא התחלה של המחרוזת. אלגוריתם זה עובד בזמן . אלגוריתם KMP משתמש בטרנזיטיביות של התאמת מחרוזות על מנת לחסוך השוואות מיותרות. בכל פעם שהאלגוריתם יתקל בנקודת חוסר התאמה בטקסט, הוא יחזור להתאים את הרישא הארוכה ביותר של התבנית המתאימה לסיפא הארוכה ביותר של הטקסט בנקודה בו נתקלנו בחוסר התאמה. 
על מנת להתאים בין הרישא הארוכה ביותר לסיפא הארוכה ביותר, נבנה טבלה ייעודית ונוכל להציץ בה בזמן קבוע.

טבלה

נרצה להוכיח שבהינתן מחרוזת האלגוריתם מוציא את טבלת הסיפות הנכונה, ו-(-1) במקום הראשון.
הערה - קל לראות .
נניח שהאלגוריתם עובד עבור ערכים קטנים מ-i, נוכיח שהוא עובד עבור i - 
מקרה ראשון - אם מתקיים  וגם  הוא אינדקס שהסיפא הארוכה ביותר הנגמרת אצלו המתאימה לרישא הארוכה ביותר זהה לסיפא באינדקס . נוכיח שאכן . הערה - לפי ההגדרה,  מקיים את זה.
קל לראות שמתקיים . נניח שמתקיים , זאת אומרת . אבל אם נוריד את התו האחרון מהסיפא והתו האחרון מהרישא, אזי יש לנו התאמה באורך לכל הפחות  באינדקס , בסתירה להנחה שהאלגוריתם צודק עבור ערכים קטנים מ-i ובפרט .
מקרה שני - . במקרה זה, מכיוון שלפי הגדרה  וגם  הוא חסם עליון לאורך הסיפא המקסימלית, אזי מתקיים בוודאות . ואכן, .
מקרה שלישי - אם מתקיים . במקרה זה, התו החדש שנוסף אינו המשך של הרישא הקודמת, ולכן נחפש רישא קצרה יותר. מכיוון שהרישא הקודמת שווה לסיפא הקודמת, אזי הסיפא הארוכה ביותר המתאימה לרישא הארוכה ביותר ברישא הקודמת, היא גם סיפא של הסיפא הקודמת. מההנחה שהאלגוריתם פועל עבור קלטים קטנים, מתקיים שאורך הסיפא החדשה המתקבלת הוא המקסימלי, ולכן כל  לא יכול להיות אורך הסיפא שאינה כוללת את התו האחרון. כלומר - גם אם האלגוריתם לא ימצא בשלב זה את אורך הסיפא הוא יתחיל באיטרציה הבאה עם , ולכן האלגוריתם תמיד יגיע בסופו של דבר למקרה הראשון או השני.
נוכיח שלא קיים  כך ש-k הוא האורך של הסיפא הארוכה ביותר הנגמרת ב- ומתאימה לרישא. אם זה אכן היה מתקיים, אז לפי הגדרה , אבל מכיוון ש- הוא אורך הסיפא הארוכה ביותר המתאימה ל-, וגם לפי הטרנזיטיביות הסיפא הנגמרת ב- זהה לסיפא הנגמרת ב-, אז למעשה , וזאת אומרת שאורך הסיפא המקסימלית הנגמרת ב- היא לפחות k, בסתירה לכך שהנחנו שהאלגוריתם צודק עבור קלטים קטנים. זאת גם למעשה ההוכחה ש-הוא חסם עליון לאורך הסיפא, שהרי  עבור  כלשהו.

הוכחת זמן ריצה

זמן הריצה הכולל של האלגוריתם הוא , כאשר הזמן הדרוש לבניית טבלה של התבנית הוא  וזמן החיפוש הדרוש הוא . נוכיח:

אלגוריתם

כאשר אנחנו מבצעים את החיפוש עצמו, בכל איטרציה של כל אחת מהלולאות יש לפחות קידום אחד של i, כלומר לא קיימת איטרציה בה i לא קודם. בנוסף, כל איטרציה של הלולאות מפעילות  פעולות, ולכן בסך הכל יש לכל היותר  פעולות.

טבלה

נסמן מונה C1 הסופר כמה פעמים עודפות האלגוריתם ביקר בתא בודד, ומונה C2 הסופר כמה פעמים האלגוריתם ביקר פעם בודדת. מתקיים  מכיוון שיש n+1 תאים בטבלה. כפי שצוין קודם, מתקיים , וגם  אם ורק אם קיימת איטרציה אחת בדיוק (כלומר C2 מקודם). בנוסף, מתקיים  לפי הגדרת הרישא. לכן, ניתן לכתוב , כלומר במקרה הגרוע יש לולאה יורדת. נחבר את התנאים - על מנת שיתקיים  צריך שיתקיים  (לפי התנאי הראשון), ועל מנת שנוכל לקדם את C1, צריך שיתקיים . בסך הכל, על מנת לקדם את C1 יש לקדם את C2, ולכן מתקיים , ומספר האיטרציות הכולל קטן מ-, או , כנדרש.