exam 09a q4

exam 09a q4

Ori (guest) 06 Feb 2012 11:51

Hi…

it was written that the question can be solved in O(n) - how is that possible? can you assist?

Thanx
Ori

Re: exam 09a q4

Asaf Schreiber 06 Feb 2012 11:54

היה נחמד אם היית כותב מה השאלה (או נותן קישור)

Re: exam 09a q4

adamsh 06 Feb 2012 12:14

היי,
אני גם לא בטוח לאיזו בחינה הכוונה בדיוק.
תוכל לרשום את התאריך של הבחינה? או קישור כלשהו לשאלה?

אדם

Ori (guest) 06 Feb 2012 12:29

sent to you via mail

adamsh 06 Feb 2012 15:28

סבבה, אז למי שמעוניין, מדובר בשאלה 4 מהבחינה מה06/03/09.

מחשבים את פונקציית הפאי של המחרוזת (אני מניח שבגלל זה הם קראו לה P בשאלה - סוג של רמז).
עכשיו, נבחן איזושהי תת מחרוזת Pi וננסה למצוא את כמות השכפולים שלה.
אז תת המחרוזת היא באורך i, ונניח שערך פונקציית הפאי שלה הוא x.
נסמן z=i-x ונבדוק האם i mod z = 0 (כלומר, האם i מתחלק ב-z). אם כן, אז Pi הוא רצף שכפולים של z התווים הראשונים. כדי לראות למה זה נכון, שימו לב שנתון לנו שיש רישא של P שהיא סיפא של Pi באורך x. תנסו דוגמאות ותראו מה קורה כאשר אתם ממקמים את שתי המחרוזות אחת ליד השניה ככה. (למשל, למה זה אומר שהבלוק הראשון של z תווים ב-P בטוח שווה לבלוק השני של z תווים של P).
אם תבינו את זה, אני בטוח שתצליחו לסיים את האלגוריתם לבד מכאן.

אדם