-2
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ Your function does not work correctly. GetSubstringIndex("abc", "abd") returns 2 instead of -1, GetSubstringIndex("aaaabc", "ab") returns 1 instead of 3. \$\endgroup\$ – Martin R Nov 19 '17 at 9:25
  • \$\begingroup\$ @MartinR Thanks for the comment, I've updated the algorithm - which edge cases might this still have? \$\endgroup\$ – dk123 Nov 19 '17 at 10:09
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Martin R Nov 19 '17 at 10:13
  • \$\begingroup\$ aside from that: this algorithm has an asymptotic complexity of n^2 \$\endgroup\$ – Vogel612 Nov 19 '17 at 14:49
1
\$\begingroup\$

First, you are using the naive way to find a substring, which is also implemented incorrectly, you can look here for an example to how to implement

Second, as for running time, your way takes(matching time) Θ(nm) where m be the length of the pattern and n be the length of the searchable text, yes all other take preprocessing and space, but their matching time is the best(on average)

Third, i suggest using Boyer–Moore string search algorithm which considered as standard and i think it can be found in boost library

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ According to codereview.meta.stackexchange.com/q/6388/35991, one should not answer question containing broken code which are likely to get closed. \$\endgroup\$ – Martin R Nov 19 '17 at 10:05
  • 1
    \$\begingroup\$ @MartinR you are right, but i was trying to help this dude \$\endgroup\$ – styx Nov 19 '17 at 10:10
  • \$\begingroup\$ @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. \$\endgroup\$ – dk123 Nov 19 '17 at 10:15
  • \$\begingroup\$ @dk123: Indeed, updated i to i=i+j makes it linear time, but also makes your algorithm not work. \$\endgroup\$ – Martin R Nov 19 '17 at 10:22
  • \$\begingroup\$ @MartinR Thanks for the confirmation - that solves all my questions. I was trying to make the code run in linear time, but seems that as a result I've made it not work. I've only realised that this code doesn't work though since you provided continuous counter-cases, thank you for replying. \$\endgroup\$ – dk123 Nov 19 '17 at 10:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.