-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\$

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.

  • 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

\$\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.