22-12-2007, 13:59
|
|
|
חבר מתאריך: 22.12.07
הודעות: 1
|
|
מציאת תת מחרוזת ארוכה ביותר
שלום לכלום
אני יושב על השאלה הזאת יומיים וכלום...
אשמח אם מישהו יעזור לי כי אני פשוט לא מצליח
את הפתרון צריך לכתוב בעזרת רקורסיה ללא שימוש בפוינטרים או לולאות
ועל ידי שימוש במערכים
זאת שאלה 8 ואחרונה בקובץ
תודה מראש
תת-מחרוזת של מחרוזת נתונה , היא מחרוזת כך שקיימת סדרה עולה ממש של אינדקסים כך שלכל מתקיים כי .
היא תת-מחרוזת משותפת של ו- אם היא תת-מחרוזת של וגם תת-מחרוזת של .
לדוגמא, נתבונן במחרוזת S:
S: ABDDR
אלו הן כל תתי המחרוזות האפשריות בשבילה.
A , B , D , R , AB , AD , AR , BD, DR, DD,BR, ABD, ADR, BDD, DDR, ADD, ABR, BDR.
כעת נניח שנתונות לנו שתי תתי מחרוזות:
S1: ABDDRGTY
S2: CDEDRGRT
אזי אלו הן תתי מחרוזות משותפות לשתיהן:
GT
DRT
DRGT
DDRGT
Etc…
מכיוון שאנו חמדנים אנו רוצים את תת המחרוזות המשותפת הארוכה ביותר. כתוב פונקציה שמקבלת שתי מחרוזות (ופרמטרים נוספים לבחירתך) מדפיסה את תת המחרוזת המשותפת הארוכה ביותר. אם יש יותר מאחת, הדפיסו אחת באופן שרירותי. ניתן להניח שגודל החרוזות אינו עולה על 20.
https://2007-uploaded.fresh.co.il/2...22/73034429.doc https://2007-uploaded.fresh.co.il/2...22/73034429.doc https://2007-uploaded.fresh.co.il/2...22/73034429.doc
|