עץ סיפות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: \1ליניארי, \1תת- |
מ קימת -> קיימת |
||
שורה 4:
עץ הסיפות של מחרוזת S באורך n הוא עץ שמקיים:
*
* הקשתות מתאימות לתתי-מחרוזות לא ריקות.
* לכל הצמתים הפנימיים (פרט אולי לשורש) יש לפחות שני בנים.
שורה 17:
בהינתן עץ סיפות עבור מחרוזת <math>S</math> באורך <math>n</math> מספר פעולות ניתנות לביצוע יעיל:
* חיפוש מחרוזות ב-<math>S</math>:
** מציאת תת-מחרוזת <math>P</math> ב-<math>S</math> באורך <math>m</math> בזמן <math>O(m)</math>
|