עץ סיפות – הבדלי גרסאות

עצי סיפות הומצאו ב-[[1973]] על ידי ווינר (Weiner) שאף הציע אלגוריתם ליניארי לבנייתם, שהוגדר על ידי [[דונלד קנות']] כ"אלגוריתם השנה של 1973". שיפור נוסף הוצע על ידי מקרייט (McCreight) ב-1976 שהציע אלגוריתם לבנייתם שזקוק לזיכרון ליניארי בלבד. בתחילת שנות ה-1990 מצא מדען המחשב הפיני [[אסקו יוקונן]] שיטה פשוטה לבניית עץ סיפות שנתון בצורה מקוונת בסיבוכיות זמן ומקום <math>O\left(n\right)</math> תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפא. רוב האלגוריתמים לעצי סיפות רצים בזמן לינאריליניארי עבור אלפבית בגודל מוגדר, כשבמקרה הגרוע ביותר זמן הריצה הוא <math>O(n\log n)</math>.

** מציאת תת -מחרוזת חוזרת הארוכה ביותר ב-<math>\Theta(n)</math>