מישהו יכול לעזור לי?

[Amitus]

הפוך..

#include<stdio.h> #include<string.h> void main() { char st[6]="tapuz"; char st2[10]="amitapuzi"; int reslt,reslt2,i=0,j,k; reslt=strlen(st); reslt2=strlen(st2); for(j=0;j<reslt2;j++) { if(st==st2[j]) { k=j; while(st==st2[j]) { i++; j++; } if(j-k==reslt) { k=1; } } } if(k==1) { printf("good"); } else { printf("bad"); } }​

 

[yossiea]

הנחה שגויה...

אם תריצי את הקוד הזה על המילים "אנציקלופדיה", "קיצוני" הוא יחזיר תשובה שלילית למרות שלפי השאלה התשובה צריכה להיות חיובית. כי הקוד הזה מניח שהמילים נמצאות אחת בתוך השנייה בסדר הנכון שלהם כלומר: "ami tapuz i", "tapuz". זה לא פותר לו את שאלה. בדומה לשאלות הקודמות, הוא צריך לכתוב אלגוריתם שמוצא את החיתוך והאיחוד של 2 קבוצות רק שבשאלה זאת הם לא מסודרות! זה הכל. מיון יעלה לו ב-n log n ואח"כ יעלה לו O של n למצוא את החיתוך. אבל לדעתי יכול להיות שאפשר בדרך יותר יעילה. אגב נזכרתי, אלגוריתם "קנוט-מוריס-פראט" לא עוזר כאן?

 

[vinney]

זה לא אלגוריתם התאמת מחרוזות?

כמו שבעצמך אמרת, זה לא מה שנדרש

 

[yossiea]

נכון, החברה האלה...

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

 

[vinney]

נו, לא ראית ממה התחיל הדיון הזה?

אני טענתי שאפשר לעשות את זה ב O של N עם משתנה עזר בגודל קבוע, נראה לי שamitus ורון לקחו לעצמם אתגר לעשות את זה, רון אפילו הצליח

 

[ron369]

"אפילו" - אל תפחיד אותו,

סה"כ זה די טריוויאלי (לא?).

 

[vinney]

חשבתי שכן

אבל תראה כמה הודעות כבר נכתבו על זה מאז

 

[ron369]

פשוט צריך לשים לב שהא"ב סופי, כנראה

(כן, הרבה הודעות

)

 

[*איתי*]

אבל עדיין זה יהיה o(n^2)...

לפי מה שהבנתי, אתה עובר על כל האותיות א"ב ועבור כל אות אתה בודק אם היא קיימת בשתי המחרוזות, ואם בקטנה יותר כל האותיות שבה קיימות גם בגדולה אז המחרוזות טובות. אז בסופו של דבר אתה עובר על כל התוים של המחרוזת הגדולה ושל המחרוזת הקטנה שזה n^2 או שלא הבנתי אתכם, תאירו את עיני? (אבל מחר! עכשיו אני עוצם אותן

)

 

[gil levi]

הסבר.

נניח שהא"ב הוא בגודל M. ממספרים את אותיות הא"ב מ1 עד M. מגדירים מערך A בגודל M ומאפסים את איבריו. כל תא במערך ישמש לנו כדי לציין כמה פעמים כל אות מופיעה בכל מחרוזת. נסמן בS את המחרוזת ה"גדולה" (זאת שמהאותיות שלה צריך לבדוק אם ניתן להרכיב את המחרוזת האחרת) ובT את המחרוזת הקטנה. נעבור על אותיות S ולכל אות L נעלה ב1 את ערך התא במערך באינדקס שמתאים לL (לחפש איזה אינדקס מתאים לL לוקח זמן קבוע כי הא"ב הוא בגודל קבוע). אח"כ נעבור על אותיות המחרוזת T ולכל אות K בT נקטין ב1 את הערך התא במערך באינדקס שמתאים לK. אח"כ נעבור על המערך A. אם באחד התאים בו יש מספר שלילי אז זה אומר שיש אות K שמופיעה יותר פעמים בT מאשר בS וזה אומר שלא ניתן להרכיב את T מאיברי S. אחרת, כל אות בK מופיעה בT לפחות פעם אחת ולכן ניתן להרכיב את T מתווי S. אני ממש עייף אז אני מתנצל אם ההסבר לא ברור.

 

[vinney]

../images/Emo45.gif

בדיוק מה שחשבתי עליו

 

[*איתי*]

עדיין! אתה עובר על כל אותיות s

וכל אותיות t! אמנם אתה עובר על שתי המחרוזות פעם אחת בלבד, ככה שזה לא n^2 אלא n, אבל עדיין לא 0(1)..

 

[ron369]

ולכך הוא התכוון... ../images/Emo13.gif

 

[vinney]

נו ברור. מי דיבר על O של 1?

 

[*איתי*]

../images/Emo163.gif../images/Emo122.gif../images/Emo9.gif

 

[gil levi]

כן, זמן הריצה הוא O zzz.

ויני כתב שצריך זיכרון נוסף בגודל O(1) zzz.

 

[gil levi]

לא לא, זה קשה מאוד!

ומי שלא עלה על זה מלכתחילה למרות שהוא כבר למד מבנ"ת לא צריך להתבייש בכלל!