שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2015 - Boyer-Moore

נתונה התבנית $A A B A A A B A A B A A$ מעל אלף-בית $\Sigma = \{A, B, C, D\}$. בנו את טבלאות $\Delta_1$ ו-$\Delta_2$ מהאלגוריתם של Boyer & Moore עבור התבנית הנתונה. | $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | | A | A | B | A | A | A | B | A | A | B | A | A | | $\Delta_2(i)$ | | | | | | | | | | | | |

רמז: עבור טבלת $\Delta_1$, מצאו את המופע האחרון של כל תו מהאלפבית בתבנית. עבור טבלת $\Delta_2(i)$, חשבו את גודל ההזזה הנדרש עבור כל "סיומת טובה" אפשרית $P[i..m]$.

פתרון: ## טבלת $\Delta_1$ — כלל התו הרע (Bad Character) הגדרה: $\Delta_1(c) = m - \max\{j : P[j] = c\}$, כאשר אם $c$ אינו מופיע בתבנית, $\Delta_1(c) = m$. כאן $m = 12$, והתבנית היא $P = \underbrace{A}_{1}\underbrace{A}_{2}\underbrace{B}_{3}\underbrace{A}_{4}\underbrace{A}_{5}\underbrace{A}_{6}\underbrace{B}_{7}\underbrace{A}_{8}\underbrace{A}_{9}\underbrace{B}_{10}\underbrace{A}_{11}\underbrace{A}_{12}$ | תו $c$ | $A$ | $B$ | $C$ | $D$ | |---|---|---|---|---| | מיקום אחרון | 12 | 10 | — | — | | $\Delta_1(c)$ | $12-12=0$ | $12-10=2$ | $12$ | $12$ | --- ## טבלת $\Delta_2$ — כלל הסיומת הטובה (Good Suffix) **הגדרה:** כאשר אי-התאמה מתרחשת במיקום $i$, הסיומת $P[i+1..m]$ כבר הותאמה. $\Delta_2(i)$ הוא ההזזה המינימלית כך שהתבנית המוזחת עדיין מכסה את הסיומת שהותאמה — על ידי מציאת **הופעה חוזרת** של הסיומת בתבנית (עם תו שונה לפניה), או **הקידומת הארוכה ביותר** של $P$ שהיא סיומת של $P[i+1..m]$. ### חישוב לכל $i$: | $i$ | **הסיומת $P[i+1..m]$** | חישוב | $\Delta_2(i)$ | |---|---|---|---| | 12 | $\varepsilon$ | הזזה מינימלית | **1** | | 11 | `A` | `A` מופיע במיקום 8, לפניו $P[7]=B \neq A$ → $12-8$ | **4** | | 10 | `AA` | `AA` מסתיים במיקום 6, לפניו $P[4]=A \neq B$ → $12-6$ | **6** | | 9 | `BAA` | הופעה ב-7..9 אך $P[6]=A=P[9]$ (פסול); קידומת `AA` תואמת סיומת → $12-2$ | **10** | | 8 | `ABAA` | הופעות ב-6..9, ב-2..5 כולן עם $P[\cdot]=A=P[8]$ (פסולות); קידומת `AA` → $12-2$ | **10** | | 7 | `AABAA` | `AABAA` = $P[1..5]$, ללא תו לפני (תחילת התבנית) → $12-5$ | **7** | | 6 | `BAABAA` | אין הופעה נוספת; קידומת `AA` תואמת סיומת `AA` → $12-2$ | **10** | | 5 | `ABAABAA` | קידומת `AABAA`=$P[1..5]$ תואמת סיומת → $12-5$ | **7** | | 4 | `AABAABAA` | קידומת `AABAA`=$P[1..5]$ תואמת סיומת → $12-5$ | **7** | | 3 | `BAABAABAA` | קידומת `AABAA`=$P[1..5]$ תואמת סיומת → $12-5$ | **7** | | 2 | `ABAABAABAA` | קידומת `AABAA`=$P[1..5]$ תואמת סיומת → $12-5$ | **7** | | 1 | `AABAABAABAA` | קידומת `AABAA`=$P[1..5]$ תואמת סיומת → $12-5$ | **7** | ### הטבלה המלאה: | $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | |---|---|---|---|---|---|---|---|---|---|---|---|---| | | A | A | B | A | A | A | B | A | A | B | A | A | | $\Delta_2(i)$ | **7** | **7** | **7** | **7** | **7** | **10** | **7** | **10** | **10** | **6** | **4** | **1** | **הכלל הכולל:** בכל שלב מחשבים $\delta = \max(\Delta_1, \Delta_2)$ ומזיזים את התבנית בהתאם.