KMP strStr with test case "mississippi" and "issip" return 4 in mac, but -1 in OJ


  • 0
    R

    class Solution {
    public:
    int strStr(string haystack, string needle) {

        int m = haystack.size();
        int n= needle.size();
        if(m==0 && n==0) return 0;
        if(m<n) return -1;
        if(m!=0 && n==0) return 0;
        if(m==1 && n==1 && haystack==needle) return 0;
        int j =0;
        int i=0;
        vector<int> p =submatch(needle);
        //int *p = strpattern(needle);
    
        while(i<m)
        {
            if(j==n) return i-j;
            
            while(j>0 && haystack[i]!=needle[j])
                j = p[j-1];
            if(haystack[i]==needle[j])
            {
                j++;
                
            }
            i++;    
        }
        if(j==n) return i-j;
        else return -1;
    }
    
    
    vector<int> submatch(string needle)
    {
        int n = needle.size();
        vector<int> p(n, 0);
        int j=0;
        for(int i=1; i<n; i++)
        {
            
            while(j>0 && needle[j]!=needle[i])
                j = p[j-1];
            if(needle[i]==needle[j])
                j = j+1;
            needle[i] = j;    
        }
        
        return p;
    }
    

    };


Log in to reply
 

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