Finding substring algorithm [closed]

I'm currently working on the below code for finding the first occurrence of a substring:

int GetSubstringIndex(const string& str, const string& search_str)
{
auto found_idx = -1;
for (auto i = 0; i < str.size(); ++i )
{
if ( str[i] == search_str[0])
{
auto j = 0;
for ( ; j < search_str.size(); ++j)
{
if (str[i+j] != search_str[j] )
{
i = i + j - 1;
break;
}
}
if (j == search_str.size())
return i;
}
}
return -1;
}


This seems to work, but usually for this problem I'm given references to various algorithms such as Robin-Karp, KMP, etc.

These algorithms I'm told require extra space, don't necessarily run in linear time depending on conditions, whereas what I'm currently using doesn't seem to use extra space + runs in linear time.

Is my algorithm incorrect, or are these other algorithms doing extra things? (thus not algorithms to return the first substring but used for other use cases - in which case I'm just comparing the wrong things)

Thanks

closed as off-topic by Martin R, Emily L., Mast, Incomputable, Vogel612♦Nov 19 '17 at 14:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Martin R, Emily L., Mast, Incomputable, Vogel612
If this question can be reworded to fit the rules in the help center, please edit the question.

• Your function does not work correctly. GetSubstringIndex("abc", "abd") returns 2 instead of -1, GetSubstringIndex("aaaabc", "ab") returns 1 instead of 3. – Martin R Nov 19 '17 at 9:25
• @MartinR Thanks for the comment, I've updated the algorithm - which edge cases might this still have? – dk123 Nov 19 '17 at 10:09
• Now GetSubstringIndex("aaabc", "aab") returns -1. And I would not consider that an "edge case". Unless I am mistaken, your approach to find a substring in linear time simply does not work. – Martin R Nov 19 '17 at 10:13
• aside from that: this algorithm has an asymptotic complexity of n^2 – Vogel612 Nov 19 '17 at 14:49

• @styx Thanks for leaving an answer, it seems that I'm currently just thinking in the wrong direction. Would you perhaps add an explanation though as to why the above would take O(nm)? (despite the code itself giving wrong output) It seems to me that since I'm updating i to i=i+j in the case of wrong matches, I'll nevertheless only take at maximum O(n) (n being the length of the string). I'm finding it difficult to understand why it's O(nm), since I'm not worst case comparing the whole query string to every single character of the original string. – dk123 Nov 19 '17 at 10:15