CODEWITHSUNDEEP
c++for-loop
dykw
dykw

Reputation: 1249

About terminate condition of for-loop

Why can't I use this?

for(int i=0; i<haystack.length()-needle.length()+1; i++)

I got error when haystack="abb" needle="abaaa".

It has no error if I use: 

int diff=haystack.length()-needle.length()+1;
for(int i=0; i<diff; i++)

This is the function:

int strStr(string haystack, string needle){
        if(needle.length()==0)
            return 0;
        if(haystack.length()==0)// || haystack.length() < needle.length())
            return -1;

        int diff=haystack.length()-needle.length()+1;
      for(int i=0; i<(haystack.length()-needle.length()+1); i++){
      //for(int i=0; i<diff; i++){
//          printf("%d %d\n",haystack.length(),needle.length());
        for(int j=0; j<needle.length(); j++){
          if(haystack.at(i+j)!=needle.at(j))
            break;

          if(j==needle.length()-1)
            return i;
        }
      }

      return -1;
    }

Upvotes: 1

Views: 52

Answers (1)

Paul R
Paul R

Reputation: 213200

You are seeing problems due to the way you are applying arithmetic to unsigned length() values. Change: 

for(int i=0; i<haystack.length()-needle.length()+1; i++)

to:

for(size_t i=0; i+needle.length()<=haystack.length(); i++)

This keeps both the left and right side of the comparison positive, avoiding the negative underflow in your original example.

Upvotes: 3

Related Questions