Missing Test Case


  • 2
    S

    Here is my implement with C++ KMP algorithm (But not correct):

    class Solution {
    public:
        int strStr(string needle, string haystack) {
            if (haystack.size() == 0) return 0;
    
            //construct the next array
            vector<int> next(haystack.size());
            next[0] = -1;
            int tmp = 0;
            for (int i = 1; i != haystack.size(); ++i) {
                if (haystack[tmp] != haystack[i]) {
                    next[i] = tmp;
                    tmp = 0;
                } else {
                    next[i] = 0;
                    ++tmp;
                }
            }
            
            tmp = 0;
            for (int i = 0; i != needle.size(); ++i) {
                while (tmp != -1 && needle[i] != haystack[tmp]) tmp = next[tmp];
                if (tmp == -1) tmp = 0;
                else ++tmp;
                if (tmp == haystack.size()) return i + 1 - tmp;
            }
            return -1;
        }
    };
    

    My program passed all test cases in 6ms. However, when I test strStr("ababcaababcaabc", "ababcaabc"), it return -1, not the correct answer 6. I think this is a missing case.


  • 0

    @ShiHaoLinag Thanks, just added your test case.


Log in to reply
 

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