Is there a bug in the C++ complier?


  • 0
    L

    I try to dual with this problem with KMP algorithm, with C++, but I found something wrong.
    The result is

    "mississippi"
    "issi"
    Output:
    -1
    Expected:
    1
    Stdout:
    next array:-1 0 0 0 
    0 m 0 i // i, haystack[i], j, needle[j] 
    -1 11 4 // j, the length of haystack, the length of needle ,printed before return the result 
    

    The problem is here.There is a while-loop in line 28 ~36,shown below

     while(i < haystack.size() && j < needle.size()) {
               
                // to detect how much times this loop is  executed
                cout << i << haystack[i] << j << needle[j] << endl;
    
                if(j == -1 || haystack[i] == needle[j]) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
    

    but I found when j = -1, this loop is broken, But actually, this shouldn't happen because at that time i = 0, j = -1, and the loop condition

    (i < haystack.size() && j < needle.size())"
    

    is satisfied, so the loop should continue instead break.Besides, I didn't write any "break" statement
    .
    Therefore, I am firmly doubt that there may be bus(s) in the C++ complier.

    all my code is listed below.

    class Solution {
    public:
    
        int strStr(string haystack, string needle) {
            if(needle.empty()) return 0;
            if(haystack.empty()) return -1;
            vector<int> next;
            for(int i = 0; i < needle.size(); i++) next.push_back(0);
            
            int i = -1, j = 0;
            next[0] = -1;
            
            // fill the "next" array
            while(j < needle.size()) {
                if(i == -1 || needle[j] == needle[i]) {
                    ++j;
                    ++i;
                    next[j] = i;
                } else {
                    i = next[i];
                }
            }
            
            for(i = 0; i < next.size(); i++) cout << next[i] << ' ';
            cout << endl;
            
            i = j = 0;
            while(i < haystack.size() && j < needle.size()) {
                cout << i << haystack[i] << j << needle[j] << endl;
                if(j == -1 || haystack[i] == needle[j]) {
                    i++;
                    j++;
                } else {
                    j = next[j];
                }
            }
            
            cout << j << ' ' << haystack.size() << needle.size() << endl;
            if(j == needle.size())
                return i-j;
            else 
                return -1;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.