Wrote an analogue of the search function of the first occurrence of the template in the text. As the first parameter, the function takes the text (C-style string) in which to search for a template. As a second parameter, a template string (C-style string) to be found. The function returns the position of the first occurrence of a template string, if it is present in the string (counting from 0), and -1 if there is no pattern in the text.

Is it possible to come up with input data that this function cannot process?

int strstr_1(const char *text, const char *pattern) { if (strlen_1(text) < strlen_1(pattern)) return -1;//проверка длины if (*text == '\0' && *pattern == '\0') return 0; // если пустые строки else if (*pattern != '\0'&& *text == '\0') return -1; else if (*text != '\0' && *pattern == '\0') return 0; bool temp = true; const char *t = text; const char*p = pattern; int i = 0; for (; *text; text++) { t = text; p = pattern; i++; while (*p && *t) { temp = true; if (*p != *t) { temp = false; break; } p++; t++; } if (temp) return i-1; } return -1; } // эти случаю обрабатываются правильно cout << "1) " << strstr_1("some", "somesome") << endl; // -1 cout << "2) " << strstr_1("", "some") << endl; // -1 cout << "3) " << strstr_1("", "") << endl; // 0 cout << "4) " << strstr_1("some", "some") << endl; // 0 cout << "5) " << strstr_1("asfasfasfasf", "asf") << endl; // 0 cout << "6) " << strstr_1("asfasfasfasf", "sfa") << endl; // 1 cout << "7) " << strstr_1("My name", " ") << endl; // 2 cout << "8) " << strstr_1("My name", "My") << endl; // 0 cout << "9) " << strstr_1("My name", "me") << endl; // 5 cout << "10) " << strstr_1("aaaaaaaf", "aaf") << endl; // 5 cout << "11) " << strstr_1(" ", "") << endl; // 0 cout << "12) " << strstr_1(" ", " ") << endl; // 0 cout << "13) " << strstr_1("", " ") << endl; // -1 cout << "14) " << strstr_1("\0", "\0") << endl; // 0 cout << "15) " << strstr_1("...my name...", "mye") << endl; // -1 cout << "16) " << strstr_1("...my name...mye", "mye") << endl; //13 cout << "17) " << strstr_1("mmmmy enammmmmye..mye!", "mye") << endl; //13

    1 answer 1

    Yes, for example aaab and aabb returns 1 for the expected -1.

    An error in while (*p && *t) and if (temp) return would help if (temp && (*t==0) otherwise there is no check that it was the pattern that ended and not the string itself.

    In general, what is the practical meaning of changing the implementation of strstr to working for O (nm) and even dirty?

    If you are critical, I recommend reading about the Knut-Morris-Pratt (KMP) algorithms about the z-function, the state machine or the like (complexity O (n + m)).

    • Thanks a lot for the tip! This is a training task, so this function will not have practical meaning. - Sergey Kusachev