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

יהי Σ האלפבית (קבוצה סופית). פורמלית, גם התבנית וגם טקסט החיפוש הם וקטורים של אלמנטים מעל Σ .Σ יכולה להיות האלף-בית האנושי הרגיל (למשל, האותיות A עד Z באלפבית הלטיני). יישומים אחרים עשויים להשתמש באלפבית בינארי ${\displaystyle (\Sigma =\{0,1\})}$ או אלפבית של DNA ${\displaystyle (\Sigma =\{A,C,G,T\})}$ בביואינפורמטיקה.

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

ניתן לסווג את האלגוריתמים השונים על ידי מספר התבניות בהן כל אחד משתמש.

נסמן ב-m את אורך התבנית, ב-n את אורך טקסט החיפוש, וב-${\displaystyle \Sigma =|K|}$; את גודל האלפבית.

אלגוריתם בויאר-מור מהווה סטנדרט בספרות עבור אלגוריתמים מעשיים לחיפוש מחרוזות.^[2]

• אלגוריתם אהו-קוראסיק (הרחבה של KMP)
• Commentz-וולטר אלגוריתם (הרחבה של בויאר-מור)
• Set-BOM (הרחבה של BOM)
• אלגוריתם רבין-קארפ

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

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

שיטה נוספת מסווגת את האלגוריתמים על פי אסטרטגית ההתאמה שלהם:^[4]

• להתאים את הרישא קודם (KMP, Shift, אהו-קוראסיק)
• להתאים את הסיפא קודם (בויאר-מור ווריאציות שלו, קומנץ-וולטר)
• להתאים את הגורם הטוב ביותר קודם (BNDM, BOM, set-BOM)
• אסטרטגיה אחרת (נאיבי, רבין-קרפ)

אך לא יעילה כדי לחפש מחרוזת אחת בתוך השנייה, היא לבדוק בכל מקום בה היא יכולה להמצא, אחד אחד, לראות אם היא שם. תחילה בודקים אם יש העתק של התבנית שמתחיל בתו הראשון של המחרוזת; אם לא, בודקים אם יש העתק של התבנית המתחיל בתו השני של המחרוזת; אם לא, נחפש החל מהתו השלישי, וכן הלאה. בדרך כלל, נצטרך להסתכל רק תו אחד או שניים לכל מיקום שגוי כדי לגלות שהתבנית לא מופיעה בו, כך שבמקרה הממוצע, זה לוקח O(n + m) צעדים, שבו n הוא אורך המחרוזת. m הוא אורך התבנית; אבל במקרה הגרוע, כמו חיפוש של התבנית "aaaab" בתוך המחרוזת "aaaaaaaaab", לוקח ${\displaystyle O(mn)}$.

בגישה זו, מונעים את החזרה אחורנית על ידי בניית אוטומט סופי דטרמיניסטי (DFA) שמזהה את התבנית השמורה אצלו בזיכרון. עלות הבניה של האוטומט יקרה—האוטומט בדרך כלל נוצר באמצעות בניית אוטומט חזקה—אבל השימוש באוטומט מהיר מאוד. לדוגמה, האוטומט סופי דטרמינסטי באיור מזהה את המילה "MOMMY". בפועל, גישה זו לעיתים קרובות מוכללת כדי לאפשר חיפוש של ביטויים רגולריים שרירותיים.

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

אלגוריתמים מהירים יותר מבוססים על עיבוד מקדים של הטקסט. לאחר בניית אינדקס לתתי-המחרוזות, למשל עץ סיפות או מערך סיפות, ניתן למצוא במהירות מופעים של התבנית. כדוגמה, ניתן לבנות עץ סיפות ב- ${\displaystyle \Theta (n)}$ זמן, ולמצוא את כל z המופעים של התבנית ב- ${\displaystyle O(m)}$ תחת ההנחה כי גודל האלפבית קבוע, וכל הצמתים הפנימיים של העץ יודעים אילו עלים נמצאים בתת-העץ שלהם. האחרון ניתן לביצוע על ידי הפעלת אלגוריתם DFS מהשורש של העץ.

שיטות חיפוש אחדות, כמו חיפוש טריגרמה, נועדו למצוא את מידת ה"קרבה" בין מחרוזת החיפוש לטקסט ולא "התאמה/אי-התאמה". דבר זה מכונה לעיתים חיפוש "עמום" (fuzzy).

• עימוד רצפים
• התאמת תבניות דחוסות

• ר. ס בויאר וג'יי. אס. מור, אלגוריתם חיפוש מחרוזות מהיר, Carom. ACM 20, (10), 262-272(1977).
• צ'ארלס א. ליזרסון, תומאס ה. קורמן, רונלד ריבסט, קליפורד שטיין. מבוא לאלגוריתמים, מהדורה שלישית. MIT Press ו-McGraw-Hill, 2009. ISBN 0-262-03293-7. פרק 32: התאמת מחרוזות, עמ'. 985-1013.

מדיה וקבצים בנושא אלגוריתמים לחיפוש מחרוזות בוויקישיתוף

• רשימה ענקית (מתוחזקת) של קישורים בנושא התאמת תבניות עדכון אחרון:12/27/2008 20:18:38
• StringSearch – אלגוריתמים לחיפוש מחרוזות בעלי ביצועים גבוהים ב-Java – מימושים של אלגוריתמים רבים לחיפוש מחרוזות ב-Java, (בויאר-מור, BNDN, בויאר-מור-הורספול, בויאר-מור-הורספול-רייטה, Shift-Or)
• StringsAndChars – מימושים מימוש של אלגוריתמים רבים לחיפוש מחרוזות (עבור תבנית אחת או יותר) ב-Java
• אלגוריתמים להתאמת מחרוזות מדויקת — אנימציה ב-Java, תיאור מפורט ומימוש C של אלגוריתמים רבים.
• (PDF) שיפורים להתאמת מחרוזות מקורבת על תבנית אחת או יותר
• Kalign2: התאמה מרובה בעלת ביצועים גבוהים של רצפים של חלבון ונוקלאוטיד, מאפשר תוספות חיצוניות
• מימוש C של עץ סיפות מבוסס חיפוש מחרוזות