שאלה במחרוזות

[MmMm20]

שאלה במחרוזות

אני צריך אלגוריתם שיקבל 3 מחרוזות, כאשר המחרוזת השניה והשלישית באותו גודל. המטרה היא להחליף כל אות שמופיעה במחרוזת 2 עם האות המתאימה במחרוזת 3, במחרוזת 1. דוגמא: "abcttxyz" "abc" "xyz" יהפוך ל- "xyzttxyz" אני חשבתי על להשתמש בטבלאות גיבוב, אבל לא יודע עד כמה תשובה זו טובה. תודה מראש.

 

[asm32]

סתם כי שיעמם לי

void xlat_str(char *inout,char src_table[],char dst_table[]) { __asm { mov esi,inout nextc: mov edi,esi mov ebx,dst_table mov edx,src_table lodsb or al,al je bye xor ecx,ecx nxlat: cmp byte ptr [edx + ecx],al je xlat_it inc ecx cmp byte ptr [edx + ecx],0h je nextc jmp nxlat xlat_it:xchg cl,al xlat stosb jmp nextc bye: } }​

 

[asm32]

הסבר

קח תוו מהמחרוזת הראשונה חפש אותו בטבלת התווים שצריך להחליף אם נמצא תשתמש במיקום שלו בטבלת התווים שצריך להחליף כדאי להוציא תוו החלפה החלף את התוו כל התהליך רץ עד שמגיעים ל 0 (סיום מחרוזת) דרך אגב מזה טבלאות גיבוב ???

 

[MmMm20]

טבלאות גיבוב

תרגום עברי מצחיק ל-hash tables. ממ בכל מקרה, הרעיון שלך הוא בסיבוכיות של n*n (באו של). יש משהו יותר יעיל?

 

[vinney]

זה בO של N

כשN זה אורך המחרוזת (מן הסתם, אתה חייב לעבור על כל אחת מהמחרוזות לפחות פעם אחת). החסם הזה הדוק (תתה) כי אתה לא צריך לעבור על כל אחת מהמחרוזות יותר מפעם אחת. סיבוכיות זכרון (פרט לזכרון הנדרש לקלט) היא כמובן קבועה. כמספר האותיות בא"ב.

 

[MmMm20]

איך זה בדיוק או של אן??

לפי מה שהבנתי הוא "רץ" על המחרוזות 2 ו-3 כמה פעמים.. או שלא הבנתי נכון..?

 

[vinney]

לא הפתרון שלו, הפתרון הנכון

 

[MmMm20]

הפתרון הנכון = הפתרון שאני הבאתי?

בכל מקרה, רציתי לדעת אם אין דרך יותר טובה.. כי המקום שהפתרון שלי לוקח הוא O של N

 

[vinney]

לא

 

[MmMm20]

ידעתי שאני צודק תודה

 

[asm32]

חחחח

היו צריכים להשאיר את זה כ hash table במקום למצוא תרגום לעברית בכל מקרה,לא שאני מומחה בחישוב יעילות של דברים,אבל דבר אחד בטוח את חייבת לעבור על כל המחרוזת תוו אחרי תוו ועבור כל תוו את חייבת לבדוק אם יש לו מחליף,אם תמצאי דרך יותר יעילה ממה שעשיתי אני ישמח לראות איך זה נעשה