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

 

עץ הסיפות של מחרוזת S באורך n הוא עץ שמקיים:

* הקשתות מתאימות לתתי-מחרוזות לא ריקות.

* לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.

 

בהינתן עץ סיפות עבור מחרוזת <math>S</math> באורך <math>n</math> מספר פעולות ניתנות לביצוע יעיל:

* חיפוש מחרוזות ב-<math>S</math>:

** מציאת תת-מחרוזת <math>P</math> ב-<math>S</math> באורך <math>m</math> בזמן <math>O(m)</math>