נתבקשנו לכתוב את strstr, ואם אפשר בצורה ליניארית...
שאלתי היא כזו...
כפי שניתן לראות אם תעיינו קצת בקוד, ישנם מקרים שהלולאה עוברת על אותו איבר פעמיים,
וזה כאשר מגיעים לפקודת הcontinue, מכיוון שזה מדלג על קידום text.

האם זה אומר שהסיבוכיות שלי היא כבר לא O של n?

קוד:

 

 
char *strstr(const char *text, const char *pattern)
{
	char *pos = NULL;
	int i = 0;
	while (*(pattern + i))
	{
		if (*text == *(pattern + i))
		{
			i++;
			if (i == 1) pos = text;
		}
		else
			if (i > 0)
			{
				 i = 0;
				pos = NULL;
				continue; //Skip text++;
			}
		text++;
		if (!(*text)) return NULL;
	}
 
	return pos;
}

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

בדרך הפרימיטיבית הזאת, כמובן שזה כבר לא יהיה O של N
BM, KMP

C pogrammers never die. They are just cast into void.

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

ציטוט:

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

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

אולי לא התעמקתי מספיק ואתה ב n*logn אבל זה בטח לא N

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

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