C מחרוזות

[didi18]

לא עולה לי רעיון אפילו...

פונקציה שמקבלת מחרוזת ותת מחרוזת ומחזירה כמה פעמים מופיעה התת מחרוזת במחרוזת

[SweeT_EviL]

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

זה בגדול.

[didi18]

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

זה בגדול.

אממ לא הבנתי =\

איך אני יודעת אם האיברים שווים?

[zurkin1232]

האם האות הראשונה במחרוזת שווה לאות הראשונה בתת-מחרוזת?

לא.

האם האות השניה במחרוזת שווה לאות הראשונה בתת-מחרוזת?

לא.

האם האות השלישית במחרוזת שווה לאות הראשונה בתת-מחרוזת?

וואו! כן! עכשיו האם שאר תת-המחרוזת מתאימה להמשך האותיות במחרוזת?

נבדוק. אם כן נרשום בצד שכן (נחזיק משתנה שישמש בתור מונה) ונמשיך...

האם האות הרביעית במחרוזת שווה לאות הראשונה בתת-מחרוזת?

...

[didi18]

האם האות הראשונה במחרוזת שווה לאות הראשונה בתת-מחרוזת?

לא.

האם האות השניה במחרוזת שווה לאות הראשונה בתת-מחרוזת?

לא.

האם האות השלישית במחרוזת שווה לאות הראשונה בתת-מחרוזת?

וואו! כן! עכשיו האם שאר תת-המחרוזת מתאימה להמשך האותיות במחרוזת?

נבדוק. אם כן נרשום בצד שכן (נחזיק משתנה שישמש בתור מונה) ונמשיך...

האם האות הרביעית במחרוזת שווה לאות הראשונה בתת-מחרוזת?

...

אני לא רוצה לעשות את זה כמו שאמרת, אני רוצה לעשות את זה עם הפונקציה strstr

[zurkin1232]

אה OK, אז חבל שלא אמרת קודם.

strstr מחזירה לך מצביע למופע הראשון של תת המחרוזת שאת מחפשת. כלומר:

char *s = "abcdabc";
strstr(s, "bc")

הקריאה הזאת תחזיר לנו בעצם s+1.

אז ככה, נריץ strstr על המחרוזת והתת מחרוזת שלנו. אם לא נמצא, פשוט נחזיר 0 (אף מופע של תת-המחרוזת לא קיים במחרוזת). אם מצאנו נוסיף 1 למונה שלנו ונתחיל לחפש את תת המחרוזת שוב, הפעם מהמקום במחרוזת שבו מצאנו את תת-המחרוזת הראשונה, פלוס 1.

כלומר, למשל בדוגמה שלנו, מצאנו את "bc" במקום ה-1 במחרוזת, ועכשיו נתחיל לחפש שוב את bc החל מהמקום ה-2 במחרוזת. הפעם strstr תחזיר לנו s+5.

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

נראה לי שכבר נתתי לך את רוב הפתרון (כנראה יותר מידי). מכאן את יכולה לכתוב את הקוד לבד?

[ofir_yair]

אם את מורשית להשתמש בפונק' strstr אז האלגוריתם אמור להיות פשוט עוד יותר:

1. while ((place=strstr(Source, SubString)!=NULL)

1.1 NumOfOccurrences++

1.2 Source=place+strlen(SubString)

האלגוריתם הזה מתאים במידה ובדוגמה הבאה תת המחרוזת aa למשל מופיעה ב-aaa פעם אחת בלבד, כלומר אי אפשר להשתמש באות אחת עבור יותר מתת מחרוזת אחת. אם במקרה שלך מספר ההופעות כאן צריך להיות 2, אז האלגוריתם של צביקה יתאים טוב יותר, כלומר באלגוריתם הנ"ל בשלב 1.2 להוסיף 1 ל-place במקום את אורך תת המחרוזת.

[didi18]

אה OK, אז חבל שלא אמרת קודם.

strstr מחזירה לך מצביע למופע הראשון של תת המחרוזת שאת מחפשת. כלומר:

char *s = "abcdabc";
strstr(s, "bc")

הקריאה הזאת תחזיר לנו בעצם s+1.

אז ככה, נריץ strstr על המחרוזת והתת מחרוזת שלנו. אם לא נמצא, פשוט נחזיר 0 (אף מופע של תת-המחרוזת לא קיים במחרוזת). אם מצאנו נוסיף 1 למונה שלנו ונתחיל לחפש את תת המחרוזת שוב, הפעם מהמקום במחרוזת שבו מצאנו את תת-המחרוזת הראשונה, פלוס 1.

כלומר, למשל בדוגמה שלנו, מצאנו את "bc" במקום ה-1 במחרוזת, ועכשיו נתחיל לחפש שוב את bc החל מהמקום ה-2 במחרוזת. הפעם strstr תחזיר לנו s+5.

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

נראה לי שכבר נתתי לך את רוב הפתרון (כנראה יותר מידי). מכאן את יכולה לכתוב את הקוד לבד?

אם strstr מחזיר לי את מקום ההופעה הראשון של התת מחרוזת במחרוזת, אני צריכה בשלב הבא לזמן את strstr עבור המקום שהמצביע נמצא בו +האורך של התת מחרוזת?

[zurkin1232]

אופיר הסביר את זה בתשובה שלו. אם עבור aaaa ו-aa את רוצה לקבל 2, אז התשובה היא כן (מקום המצביע + אורך תת-מחרוזת). אם את רוצה לקבל 3, אז התשובה היא לא (מקום המצביע + 1).

[didi18]

אופיר הסביר את זה בתשובה שלו. אם עבור aaaa ו-aa את רוצה לקבל 2, אז התשובה היא כן (מקום המצביע + אורך תת-מחרוזת). אם את רוצה לקבל 3, אז התשובה היא לא (מקום המצביע + 1).

תודה

int func(char *s, char *sub)
{
	int i, count=0;
	char *p;

	for(i=1; i<N; i++, p++)
	{
		p=strstr(s,sub);
		if (p!=NULL)
		{
			count++;
			s=p+1;
		}
	}

	return count;
}

[zurkin1232]

משהו פה חסר לי.

מה בדיוק תנאי העצירה? מהו N? האם N הוא אורך המחרוזת s? אם כן צריך לוודא שזהו משתנה גלובלי (או קבוע).

כמו כן, בהנחה ש-N הוא אורך המחרוזת, האלגוריתם לא יעיל. נניח ש-sub לא נמצא כלל ב-s, בכל זאת את מבצעת את הלולאה N פעמים (למעשה N-1 פעמים). מיותר.

הנה פתרון אלטרנטיבי

int func(char *s, char *sub)
{
  int count = 0;

  while (s != NULL)
  {
    s = strstr(s, sub);
    if (s != NULL)
    {
      ++count;
      ++s;
    }
  }

  return count;
}

מה ששונה כאן הוא תנאי העצירה. אחרי כל קריאה ל-strstr אני בודק האם s הוא NULL, כלומר האם לא מצאנו עוד מופעים של sub ב-s.

אם sub לא מופיע בכלל ב-s, אז נקרא ל-strstr פעם אחת, הוא יחזיר NULL, ומיד נצא מהלולאה.

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

int func(char *s, char *sub)
{
  int count = 0;

  while ((s = strstr(s, sub)) != NULL)
  {
    ++count;
    ++s;
  }

  return count;
}

[ofir_yair]

הנה עוד הצעה ללא שום ערך מוסף על הפתרונות המצויינים שצביקה כבר הציע, סתם כי נראה לי שהפתרון הרקורסיבי פשוט מתבקש כאן:

int Occur(const char* sub, const char* source){
	char* place;
	if ((place=strstr(source,sub))!=NULL){
		return (1+Occur(sub,place+1));
	}
	else{
		return 0;
	}
}

[didi18]

משהו פה חסר לי.

מה בדיוק תנאי העצירה? מהו N? האם N הוא אורך המחרוזת s? אם כן צריך לוודא שזהו משתנה גלובלי (או קבוע).

כמו כן, בהנחה ש-N הוא אורך המחרוזת, האלגוריתם לא יעיל. נניח ש-sub לא נמצא כלל ב-s, בכל זאת את מבצעת את הלולאה N פעמים (למעשה N-1 פעמים). מיותר.

הנה פתרון אלטרנטיבי

int func(char *s, char *sub)
{
  int count = 0;

  while (s != NULL)
  {
    s = strstr(s, sub);
    if (s != NULL)
    {
      ++count;
      ++s;
    }
  }

  return count;
}

מה ששונה כאן הוא תנאי העצירה. אחרי כל קריאה ל-strstr אני בודק האם s הוא NULL, כלומר האם לא מצאנו עוד מופעים של sub ב-s.

אם sub לא מופיע בכלל ב-s, אז נקרא ל-strstr פעם אחת, הוא יחזיר NULL, ומיד נצא מהלולאה.

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

int func(char *s, char *sub)
{
  int count = 0;

  while ((s = strstr(s, sub)) != NULL)
  {
    ++count;
    ++s;
  }

  return count;
}

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

תודה =]