C - חיפוש תת-מחרוזת בתוך מחרוזת - תקוע

[laufgas]

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

הסבר קצת יותר מפורט: אם למשל קבעתי שהמחרוזת היא acbdacss והתת-מחרוזת היא ac אז הפלט צריך להיות 2 כי ac מופיע פעמיים במחרוזת.

הנה קוד התוכנית

#include <stdio.h>

int foon(char *shorter, char *longer) /*this is the function that calculate
                               the number of times the sub string is showing*/
{
  int counter=0; /*the counter that should count the number of times*/
  char *backup=shorter;
  while(*longer!='\0') 
{
              while(*shorter!='\0')
              {
                        if(*longer==*shorter) 
                        {
                                   shorter++;
                                   longer++;
                                   }
                        else {        
                           shorter=backup;
                           longer++; 
                           } 

               }
                counter++;
                shorter=backup;


}

return counter;

}






int main()
{
  char lstring[10]="ac";
  char string[11]="acbacbacb";
  int counter;
  counter=foon(lstring, string);
  printf("The sub-string appears to be in the string %d times.", counter);
}

[Ghosthunter]

1) אתה צריך לבדוק במקום כלשהו אם אכן הגעת לסוף הSHORTER ורק אז לקדם את המונה שלך.

2) כדי לשמור "גיבוי" גם לארוך יותר, במקרה שאתה מחפש את aa בתוך aaa(מופיע פעמיים), ואפילו במקרה יותר חמור - כאשר גילית שזו לא המחרוזת, אלא רק חלק ממנה.aab בתוך aaab.

[pig_750]

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

ככה אני הייתי כותב את זה:

#include <stdio.h>


#define MAIN_LEN	102
#define SUB_LEN		52

main()
{
	char main_string [MAIN_LEN];
  char sub_string [SUB_LEN];

	short i,x;	
	short chr_match; 
	int  found = 0;



	printf ("Enter the first string (%d characters max): ",MAIN_LEN-2);
	fgets (main_string, MAIN_LEN, stdin);

	printf ("Enter the second string (%d characters max): ",SUB_LEN-2);
	fgets (sub_string, SUB_LEN, stdin);


	/* Remove the new line character */
	main_string[strlen(main_string)-1] = '\0'; 
	sub_string[strlen(sub_string)-1] = '\0';




	for (i = 0; main_string[i] != '\0' ; i++) 
		{
			for (x = 0; sub_string[x] != '\0'; x++ ) 
				{	
					chr_match = (main_string[i+x] == sub_string[x]);
					if (!chr_match) break;              
				}


			if (chr_match) found++; 


		}

	puts ("");	


	if (found)
		printf("The sub string \"%s\" appears in the string \"%s\" %d times",sub_string,main_string,found );
	else
		printf("Sorry, \"%s\" does not contain the string \"%s\" ",main_string, sub_string); 


	fflush (stdin);
	getchar();

}	

לא בטוח שזה 100% עובד כי בדקתי את זה אולי פעמיים.

ניסיתי לשמור את זה פשוט אז לא בדקתי מקרים מוזרים כמו: " "

או האם המחרוזת השניה ארוכה מהראשונה וכו'

אגב כשאתה מקבל פוינטרים מומלץ שתבדוק שהם לא NULL .

[Boomerang]

יש גם מקרה יותר גרוע, כמו abac בתוך ababac.

בדרך ה"פשוטה", אתה צריך לחפש את תת-המחרוזת מכל תו בנפרד.

יש גם אלגוריתם די יפה שעושה את זה על suffix tree, אבל בנייה של suffix tree זה לא דבר פשוט במיוחד (בטח שלא פשוט אם רוצים לעשות את זה בצורה יעילה).

[Niseg]

תקרא על QSFSORT (quick subfix sort) אני חושב שככה כותבים את זה.הוא עושה מיון על כל השורה ושומר את ה אינדקסים לפי הסדר (די מסובך להבין את הקוד כעיקרון זה radix sort ) ואז אפשר לחפש חיפוש בינארי יחיד על האינדקסים ששמרת. השורות המתאימות יהיו אחת אחרי השניה.

משתמשים בזה בBSDIFF שמיצר קבצי patch . אני די חרשתי אותו כי הקוד די שימושי למרות שחלקים ממנו לא יעלים כלכל. בכל מקרה הקוד של הdiff אוכל בערך פי 17 מהעורך של השורה המקורית . זה יכול להיות מפלצתי אם הקובץ ענק.

[pig_750]

אין לי מושג מה זה suffix tree או QSFSORT , מה היתרון שזה מביא לי לעומת 2 לולאות for פשוטות?

[Ghosthunter]

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