למען הסר ספק, מספיק למצוא מופע אחד של P ולא את כל המופעים כמו KMP, נכון?
סליחה שכחתי להפוך, השאלה הייתה: למען הסר ספק, מספיק למצוא מופע את של P ולא את כל המופעים כמו בKMP, נכון?
בשאלות 7,8 מותר לעשות שינוי לאלגוריתמם עצמו?
זה מאוד פשוט אם מוסיפים איזשהי התייחסות עם if בלולאת ה- for בפונקציית KMP שלא משנה את התנהגות שאר הפונקציה.
השאלה אם זה גורר עכשיו הוכחה מחדש של האלגוריתם או משהו כזה
Hi Yuval,
It is probably correct (since these two variations are expressible in terms of Finite Automata) but if you do such a thing, you'll indeed have to reprove correctness.
The "intended" solution uses KMP as a black box.
I solved 7 by using KMP as a black box (splitting up the pattern into sub-patterns), but I couldn't figure out a solution for question 8 that uses KMP as a black box.
Could you drop me a hint? (or two hints, or the solution :P)