שאלה לגביי KMP

שאלה לגביי KMP

alona (guest) 24 Jan 2011 20:58

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

ויכול להיות שאם הייתי צריכה לחשב הייתי צריכה פשוט במקרה של התאמה להחזיר את
j?
תודה :)

Re: שאלה לגביי KMP

adamsh 24 Jan 2011 21:40

היי,

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

אם הבנת את האלגוריתם, אני מקווה שהבנת גם את מה שרשמתי. אחרת את מוזמנת לשאול.
אדם

alona (guest) 24 Jan 2011 21:47

הבנתי.
אז אפשר להניח שבהרצה כבר חישבו לנו אותו? או לכתוב איזה שורה בפתרון על איך איך אני מחשבת אותו?.

Re: שאלה לגביי KMP

adamsh 24 Jan 2011 21:51

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