How can I find if a substring is present in a string or not without using find() function?

Question

How can I find if a substring is present in a string or not without using find() function? Is there any efficient way to find the substring than using find() function? `

#include <bits/stdc++.h>
using namespace std;

int isSubstring(string s1, string s2)
{
     int M = s1.length();
     int N = s2.length();
     for (int i = 0; i <= N - M; i++) {
          int j;
      for (j = 0; j < M; j++)
        if (s2[i + j] != s1[j])
            break;

      if (j == M)
        return i;
     }

     return -1;
}

int main()
{
     string s1 = "for";
     string s2 = "geeksforgeeks";
     int res = isSubstring(s1, s2);
     if (res == -1)
    cout << "Not present";
     else
    cout << "Present at index " << res;
     return 0;
}

//I found this code on Geeks for geeks but its time complexity is O(M*(N-M)). Can it be reduced?

Please take some time to read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) The geekforgeeks site has a very bad reputation around here, for teaching bad habits, bad code, and sometimes even invalid code. — Some programmer dude, Feb 19 '23 at 11:02
Please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and then *never* include that header again and you should probably also stop learning from whatever source told you to do that. See also [Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Jesper Juhl, Feb 19 '23 at 11:56

score -1 · Answer 1 · answered Feb 19 '23 at 14:06

You could of course iterate over one string and compare every possible substring with the substring you search for.

BUT it is in general better to use methods from the STL because they are well-tested and in most cases faster than your own implementation.

How can I find if a substring is present in a string or not without using find() function?

1 Answers1