עץ סיפות

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).
עץ סיפות עבור המחרוזת BANANA מרופדת עם $. מצביעי הסיפה מקווקוים.
עץ סיפות עבור המחרוזת BANANA מרופדת עם $. מצביעי הסיפה מקווקוים.

במדעי המחשב עץ סיפות הוא מבנה נתונים המאפשר חיפושים מהירים של תת מחרוזות כלשהי של מחרוזת נתונה. אפשר לחשוב עליו כעל עץ תחילות המכיל את כל הסיפות של המחרוזת, לאחר כיווץ שרוכים.

יוקונן מצא שיטה יעילה לבניית עץ סיפות בסיבוכיות זמן ומקום O\left(n\right) תוך שימוש בכמה אופטימיזציות, כולל מצביעי סיפה. מבנה נתונים שקול אך כנראה יותר יעיל במעשה הינו מערך סיפות (הייצוג כמערך יותר קומפקטי ויעיל, אולם בעל אותה סיבוכיות אסימפטוטית).

ערך זה הוא קצרמר בנושא מחשבים. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.

מקור: http://he.wikipedia.org../../../%D7%A2/%D7%A5/_/%D7%A2%D7%A5_%D7%A1%D7%99%D7%A4%D7%95%D7%AA.html