שלום לכולם

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

לדוגמא עבור הקלט abcdef ו abdefg

יוחזר 3 def

נתון נוסף המחרוזות ממוינות בסדר עולה

ההגבלה שיש היא לא ניתן לעבור על המחרוזת יותר מפעם אחת למי שמבין סיבוכיות O(n

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

עכשיו הפתרון שאני מצאתי זה להחתיל ממקום 0 להשוות בין התווים במידה והתו באחת המחרוזות גדול מהתו השני אז לקדם את הINDEX של התו הקטן באחד ככה להשוות עד אשר נגמר הקלט

הבעיה בפתרון היא עבור קלט

aabbbcde

abbbbcdg

הוא לא יחזיר את אורך הקלט האמיתי אלא 2 cd כי באחת ההשוואות הוא משווה c עם b ואז מדלג ומאפס

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

נ.ב מקווה שהייתי ברור בהסבר

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

כשאתה אומר o(n), מה זה n?

סכום אורכי תתי המחרוזות?

כן n זה אורך המחרוזת

היי isildur רעיון טוב לחפש בgoogle אבל לא מצאתי שם משהו שיעזור לי בפתרון

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

כי הסיבוכיות שלהם גדולה מידי

מכיר אולי איזה אתר עם קוד כזה או דומה?

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

למה שלא תמשיך מהאי- שוויון שמצאת?(לא מאתחלים את האינדקס בלולאה השניה).

תבדוק את זה:

int mani=-1, maxl=0, lastl=0, i, j;
for(i=0, j=0;i<n;i+=lastl+1)
{
	for(;a[i]==b[j];j++);
	lastl=j-i-1;
	if(lastl>maxl)
	{
		maxl=lastl;
		maxi=i;
	}
}
if(mani<0)
	cout<<"No Match";
else
{
	cout<<"Match: "<<maxi<<", "<<maxl;
}

רשמתי את זה עכשיו. יש בזה קצת בעיות, ולא נראה לי שזה יעבוד, אבל זה הרעיון.

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

אבל זה לא יעזור לי מהסיבה שפתרון רץ בסיבוכיות של N*N יש 2 לולאות אחת בתוך השניה

אני צריך לפתור את הבעיה עם לולאה אחת

אתה שומר כמה משתנים:

אינדקסים של התו הנוכחי בכל מחרוזת והאורך של תת-המחרוזת הנוכחית (כולם מאותחלים ל- 0)

אינדקסים של תחילת תת-המחרוזת הכי ארוכה עד עכשיו והאורך שלה (גם מאותחלים ל-0)

אתה מתקדם במקביל על שתי המחרוזות -

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

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

אגב, O(n) לא אומר שמותר לך לעבור רק פעם אחת על הקלט, אלא שמותר לך לעבור על הקלט רק מספר סופי של פעמים (שלא תלוי באורך הקלט)

אגב, O(n) לא אומר שמותר לך לעבור רק פעם אחת על הקלט, אלא שמותר לך לעבור על הקלט רק מספר סופי של פעמים (שלא תלוי באורך הקלט)

o(1)

אבל זה לא יעזור לי מהסיבה שפתרון רץ בסיבוכיות של N*N יש 2 לולאות אחת בתוך השניה

אני צריך לפתור את הבעיה עם לולאה אחת

שים לב- מה שעשיתי זה o(n). אסור לך לספור את הסיבוכיות שלך ע"י מספר הלולאות המקוננות. זה פשוט טעות.

אם תשים לב, אני לא מאתחל את J בלולאה ה"קטנה", וממשיך מאותו מקום שהייתי בו.

ד.א. רק שתדע- גם o(n) זה טעות. אתה צריך להבין. אם יש לך 2 מערכים באורך שונה, ואתה רץ על שניהם, אז זה חייב להיות לפחות o(n+m) או o(max(n,m)).

אתה בטוח שזה אמור להיות o(n) כי לא נראה לי שאפשר לעשות את זה בסיבוכיות הזו.

כדי למצוא אם יש בכלל תת מחרוזת משותפת אתה צריך לבדוק כל אות במחרוזת אחת האם היא נמצאת במחרוזת השנייה (במקרה הגרוע לא תהיה אף אות משותפת לשני המחרוזות) לכן הסיבוכיות חייבת להיות o(n*m) כאשר n היא אורך מחרוזות אחת וm היא אורך המחרוזת השנייה.

כן אני בטוח שזה צריך להיות O של n יש נתון שעוזר לנו לא לעבור על המחרוזת פעמיים וזה שזה מסודר בסדר עולה

אם הבנתי אותך נכון זה הפתרון שהצעת Boomerang

int max_common_substr(char *str1, char *str2)

{

int cout_str=0, max_str = 0;

while ((*str1) && (*str2))

{

if (*str1 == *str2)

{

cout_str++;

str1++;

str2++;

}

else

{

if (max_str < cout_str)

max_str = cout_str;

cout_str = 0;

if (*str1 > *str2)

str2++;

else

str1++;

}

}

if (max_str < cout_str)

return cout_str;

return max_str;

}

נראה ככה... והאמת - נראה לי שזה עובד בדיוק כמו מה ש- ghosthunter הציע, רק קצת יותר קריא.

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

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

למישהו יש דרך לפתור את הבעיה הזאת ?

אופס. צודק.

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

כלומר - נניח עד עכשיו המחרוזת המשותפת היא aabb ועכשיו קראת b במחרוזת אחת ו- c במחרוזת השניה.

בגלל שיכול להיות שתת מחרוזת חדשה מתחילה ב- b הראשון, אתה מזיז את 'מיקומי ההתחלות' 2 מקומות אחורה מהמקום הנוכחי (שזה מספר הפעמים שהאות האחרונה חזרה), ואז מקדם את המיקום הנוכחי במחרוזת השניה עוד צעד קדימה ובודק אם הוא שווה לאות במיקום הנוכחי במחרוזת הראשונה.