מכירים את האלגוריתם הנאיבי להתאמת מחרוזות ?
נניח יש לי טקסט ארוך T , ומחרוזת קצרה S .. אני רץ עד שאני שם לב שהאות הראשונה בS מתאימה לאות שאני נמצא בה בT.
אם זה מתאים ,אני ממשיך לאות השניה .. נניח באות החמישית זה נדפק .. אני ממשיך בT מהמקום שבו מצאתי את ההתאמה הראשונה.
לכן בהנתן והאורך של S זה m והאורך של T זה n הסיבוכיות היא :
O(n*m) dd
כל זה לידע כללי, עכשיו השאלה :
נניח שהמחרוזת P והטקסט T הם מחרוזות באורך m וn בהתאמה, שנבחרו באקראי מאלפבית בין d תווים , כאשר d מכיל יותר מ2 תווים.
הראה כי תוחלת ההשוואות בין תווים בודדים (באלגוריתם הנאיבי) היא :
(n-m-1)*\frac{(1-d^{-m})}{(1-d^{-1})}<= 2(n-m+1)
אין לי מושג איך להתחיל לחשב את זה.. אפשר קצת כיוון או עזרה ?
אגב, איך אני הופך את זה שיראה כמו נוסחא ?