שאלת אלגוריתם

[liorhal]

שאלת אלגוריתם

יש לכם רעיון לאלגוריתם לפונקציה שבהנתן מחרוזת(char*) ואורכה, תדפיס את כל תתי המחרוזת של המחרוזת (בהנחה שאין כפילויות): למשל: "אבג" יחזיר: "" , "א" , "ב" , "ג" , "אב" , "אג" , "בג" , אבג"

 

[IsraeliSecretToilets]

בהנחה והמחרוזת לא ארוכה במיוחד..

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

כלומר יש לך שני מצביעים. בתחילה שניהם עומדים בהתחלה. את המצביע השני אתה מקדם כל הזמן תו אחד קדימה ומדפיס את המחרוזת בין שני המצביעים. לאחר מכן שני המצביעים עומדים על התו השני וגם הפעם את השני מקדמים כל פעם תו אחד קדימה ומדפיסים. אח"כ שני המצביעים מתחילים בשלישי וכן הלאה. זה לא האלגוריתם הכי יעיל שיש, אבל לדעתי הוא יספק אותך. אם אתה רוצה משהו באמת יעיל ומהיר תשתמש ב-suffix tree, אבל לדעתי הייתרון שלו הוא ברור רק כאשר המחרוזות ממש גדולות. מה גם, הוא לא ממש טוב לצורכי הדפסה, אלא רק לצורכי עיבוד מחרוזות בזיכרון.

 

[liorhal]

תשובה לא נכונה

התת מחרוזת לא חייבת להיות רצופה. שים לב בדוגמא שנתתי: מ-"אבג" נוצר גם "אג" !! בכל מקרה תודה על המאמץ. כמובן שיש את הפתרון בעזרת משחקי ביטים: 00000001 מציין להכניס איבר ראשון בלבד. 00000010 הכנסת איבר שני בלבד. 00000011 הכנסת איבר ראשון ושני וכן הלאה, בעזרת סבירה בינארית. אבל אני מחפש תשובה אחרת. משהו רקורסיבי אולי.

 

[כלמנסע]

הגדר מה זה אצלך תת מחרוזת

הגדר מה זה אצלך תת מחרוזת

 

[ahab]

רעיון רקורסיבי

בהינתן מחרוזת כלשהי X, תתי המחרוזות של X הן כל תתי המחרוזות שכוללות את האות הראשונה של X ובנוסף כל תתי המחרוזות שאינן כוללות את האות הראשונה של X. מכאן ההמשך די פשוט...

 

[IsraeliSecretToilets]

הוצאת לי את המילים מהמקלדת ../images/Emo3.gif

 

[liorhal]

יש לכם רעיון ?

לכתוב את זה בLISP או בכל שפה אחרת שעובדת עם רשימות זה קל. איך כותבים את זה בC ?

 

[IsraeliSecretToilets]

ככה ../images/Emo3.gif

#include <string.h> #include <stdio.h> #include <stdlib.h> /* prints all substrings of <str> * using temporary memory <temp> and <loc> */ void recursive_print_substr(char* str, char* temp, int loc) { if( '\0' == (*str) ) { /* stop condition - str is an empty string */ printf( temp ); } else { /* call recursive print not including the first char */ recursive_print_substr(str + 1, temp, loc); /* add the first char and call recursive print */ temp[loc] = *str; temp[loc + 1] = '\0'; recursive_print_substr(str + 1, temp, loc + 1); temp[loc] = '\0'; } } /* prints all substrings of <str> of length <len> */ void print_substr(char* str, int len) { char* temp; /* allocate and initialize temporary memory */ temp = (char *) malloc( len + 1 ); if( NULL == temp ) { fprintf(stderr,"Error allocating memory.\n"); exit(EXIT_FAILURE); } temp[0] = '\0'; /* call recursive print funcion */ recursive_print_substr(str, temp, 0); /* free allocated memory */ free(temp); }​

תקרא לפונקציה print_substr, היא תקצה זיכרון זמני, תקרא לפונקציה recursive_print_substr וזו תדפיס בצורה רקורסיבית את כל תתי המחרוזות. מקווה שאין פה באגים

 

[liorhal]

יפה מאד

אני חושב שזה עובד. כבוד

 

[ron369]

אני לא בטוח לגמרי, אבל אני חושב שזה

בדיוק מה שהוא אמר, רק בצורה רקורסיבית. כלומר...אתה מקבל מחרוזת Y, ואז אתה עושה מחרוזת חדשה X באורך 1 פחות, אבל כשהתו הראשון הוא פעם "חי" ופעם "מת". 1X ו 0X ... ובסוף, כמובן שזה יוצא רגיל (ב3 נגיד): 111,110,101,100,011,010,001,000...(אם לא טעיתי) ככה שבעצם רק עשית כמוהו, בצורה רקורסיבית. (או שאני טועה?)

 

[Zack DA]

רק, תמיר את זה ללולאה כדי שהתוכנית

שלך לא תקרוס. אתה שומר כאן פרמוטציות שלמות בזיכרון....

 

[IsraeliSecretToilets]

לא ממש ../images/Emo12.gif

המימוש של האלגוריתם שהוא הציע (לפחות המימוש שלי) דורש (O(n זיכרון, כאשר n הוא אורך המחרוזת.

 

[Zack DA]

תחשוב שוב....

 

[IsraeliSecretToilets]

לא לא...

אתה תחשוב שוב

 

[Zack DA]

זה לקח בשבילי, לקרוא עד הסוף -

לפני שאני מגיב. התחלתי לקרוא וחשבתי שאתה מתכוון לפתרון אחר. מתנצל. אני צריך לשהות יותר זמן בפורום...

 

[vinney]

מה זה תת מחרוזת אצלך?

לפי מה זאתה אומר זה קבוצת הקבוצות החלקיות לקבוצה, ואז האלגוריתם הרקורסיבי שקיבלת לא מוצלח... או שאני טועה?

 

[IsraeliSecretToilets]

נראה לי שהוא מתכוון..

ממש למונחים הידועים באנגלית מעולם עיבוד המחרוזות. subsequence מוגדרת להיות סדרה רצופה של תוים המופיעים באותו סדר כמו במחרוזת המקורית. substring (תת מחרוזת) מוגדרת להיות תת סדרה (לאו דוקא רצופה) של תוים המופיעים באותו סדר כמו במחרוזת המקורית.

 

[vinney]

הא ../images/Emo13.gif אז שידבר באנגלית ../images/Emo13.gif

אני חי בעולם ה sub-set

 

[the another one]

ככה :

רוץ עם שני אינדקסים. אינדקס א' נשאר במקום 1 בזמן שאינקדס 2 רץ על המחרוזת. כל התווים בין שני האינדקסים האלו הם תת מחרוזות. ברגע שאינקדס ב' בגיע לסוף המחרוזת, תקדם את אינקדס א' ב 1 ואינדקס ב' יהפוך להיות שווה לאינדקס א'. כך תמשיך עד שאינדקס א' יגיע לסוף המחרוזת. cat-fish ?

 

[IsraeliSecretToilets]

רק חבל שלא..

קראת את כל השרשור