יש לי שאלה בקשר לתרגיל הזה

באלגוריתם מילולי, מותר לי להשתמש בפונקציות שקיימות על מחרוזת? יעני אני יכול לרשום באלגוריתם המילולי נניח אורך_מחרוזת (קיימת פונ' srtlen או משהו כזה.. )?

תודה!

נראה לי שהרעיון הוא שאתה אמור להתייחס למחרוזת כמערך/מחסנית של תוים בודדים.

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

האמת, זה קצת יותר מסובך מזה.

קח לדוגמא מצב שבמחסנית יש את המחרוזת ABABAC (משמאל לימין) ואתה מחפש את תת המחרוזת ABAC.

המקום שבו תגלה שהמחרוזת הראשונה לא מתאימה לך יהיה כשתקרא את ה- B השני, אבל תת המחרוזת ה"נכונה" מתחילה ב-A שלפניה.

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

אפשר גם בלי

סליחה על הבורות אבל,

מה הכוונה מחסנית?

לפי הספר:

המחסנית היא טיפוס נתונים המאחסן איברים מסוג מסוים. כדי שיהיה אפשר להוסיף איברים למחסנית ולהוציא אותם ממנה, נגדיר את הפעולות: דחוף-למחסנית, שלוף-ממחסנית. הקשר בין פעולות אלו הוא המייחד את הטיפוש: אם נדחוף למחסנית איבר ומיד לאחר מכן נבצע שליפה, יתקיימו שני תנאים:

א. האיבר שנשלוף יהיה אותו איבר שזה עתה דחפנו.

ב. מצב המחסנית לאחר השליפה יהיה זהה למצבה לפני הדחיפה.

ניתן לראות במחסנית קופסה סגורה בעלת פתח יחיד, שדרכו נעשות פעולות הדחיפה והשליפה. הטיפול באיברים דרך פתח יחיד זה יוצר מצב שבו איבר שנכנס אחרון יוצא ראשון. גישה כזו לאיברים נקראת LIFO, ראשי תיבות של: Last In First Out.

לפי הספר:

המחסנית היא טיפוס נתונים המאחסן איברים מסוג מסוים. כדי שיהיה אפשר להוסיף איברים למחסנית ולהוציא אותם ממנה, נגדיר את הפעולות: דחוף-למחסנית, שלוף-ממחסנית. הקשר בין פעולות אלו הוא המייחד את הטיפוש: אם נדחוף למחסנית איבר ומיד לאחר מכן נבצע שליפה, יתקיימו שני תנאים:

א. האיבר שנשלוף יהיה אותו איבר שזה עתה דחפנו.

ב. מצב המחסנית לאחר השליפה יהיה זהה למצבה לפני הדחיפה.

ניתן לראות במחסנית  קופסה סגורה בעלת פתח יחיד, שדרכו נעשות פעולות הדחיפה והשליפה. הטיפול באיברים דרך פתח יחיד זה יוצר מצב שבו איבר שנכנס אחרון יוצא ראשון. גישה כזו לאיברים נקראת LIFO, ראשי תיבות של: Last In First Out.

אם אני מבין נכון את התנאים של השאלה , אסור להוציא את כל האיברים ? אבל אני מניח שאי אפשר לפתור הבעיה ללא הוצאת האיברים , לכן הדגש על המילה "כל" לכן יש להעזר במתודה נוספת של מחסנית שנקראת poke (להציץ) והיא מחזירה לך את האיבר האחרון שהוכנס למחסנית אבל מבלי להוציא אותו (להבדיל מ- Pop) לכן במקרה הכי קיצוני אם יש התאמה אזי היא תיהיה כאשר האיבר הראשון שהכניסו למחסנית זהה לאיבר האחרון במחרוזת הנבדקת אבל בעזרת Poke נשלים את ההשוואה מבלי שרוקנו את המחסנית לגמרי