match a short string within a long string in c++

Question

I tried to write a class called Mystring which basically does everything std::string class can do. Right now I'm trying to write a MyString::rfind function which will match a short string with the long string(just like the rfind function for string class). However, when I run the code nothing gets printed out in the console. Can anyone spot where the problem is?

//cpp 
size_t MyString::rfind(const MyString& str, size_t pos) const {
    if (str.size() == 0 && pos < s.size()) { return pos; }
    if (str.size() == 0 && pos > (s.size() - 1) ) { return s.size(); }
    size_t a = std::min(pos, (s.size() - 1));
    for (size_t i = a; i >= 0; --i) {
        if (s[a] == str.s[0]) {
            for (size_t b = 1; b < str.size(); ++b) {
                if (s[i + b] != str.s[b]) { break; }
                if (b == (str.size() - 1)) { return i; }
            }
            return -1;
        }

    }
    return -1;
}


//main
int main(){
 
const MyString testMyString = "0123456789";
cout << testMyString.rfind("647")<< endl;
return 0;
}

Your class doesn't have any constructor accepting a `const char*` so how does this compile? — UnholySheep, Aug 08 '20 at 18:40
*basically does everything std::string class can do.* -- No it cannot. Note that `std::string` is a specialization of [std::basic_string](https://en.cppreference.com/w/cpp/string/basic_string). So are you ready to implement all of those functions? — PaulMcKenzie, Aug 08 '20 at 18:43
You can also add an early exit if `pos + str.size() > s.size()`, which would mean you wouldn't need the `min` call. — Mooing Duck, Aug 14 '20 at 00:10

score 3 · Accepted Answer · answered Aug 08 '20 at 18:58

3

Your problem is here in the rfind() function:

for (size_t i = a; i >= 0; --i) {

The minimum value size_t can reach is 0. If you decrement it when it is 0, you wrap around to the largest value again. On my 64 bit system that value is 18446744073709551615. As you can see this value is greater than 0 so the loop never finishes.

Try this piece of code and you will immediately see your mistake:

size_t x = 0;
x--;
cout << x; // What do you think it will print?

answered Aug 08 '20 at 18:58

Waqar

8,558
4
35
43

ok I see. It will print the biggest int. So all I need to do it to change `i >= 0` to `i>0`? – BigMoose Aug 08 '20 at 19:03
Yes, that will make it work. However, for the current code you will probably see `18446744073709551615` as output. – Waqar Aug 08 '20 at 19:06
1

@Waqar Will that really work? Will it find a match at the beginning of the string, or stop before it gets there? – Barmar Aug 13 '20 at 23:43
@Barmar Will it? I don't think so. The question was about being stuck in an infinite loop. And I answered about just that leaving the rest of the logic to OP. :) – Waqar Aug 14 '20 at 04:53
So you fixed one bug but replaced it with a different bug? And didn't provide any insight about how to fix the new bug. – Barmar Aug 14 '20 at 04:54
No. `i > 0` will work,but there will need to be a few modifications. – Waqar Aug 14 '20 at 04:56

match a short string within a long string in c++

1 Answers1