# 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

• 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