Time O(M+N) with O(M) space


  • 0
    N

    vector<int> prefix(string s){
    vector<int> prefix(s.length(),0);
    int j=0;

    for(int i=1;i<s.length();i++)
    {
        if( s[i] == s[j] )
        {
            prefix[i]=j+1;
            j++;
        }
        else{
            
            while(s[j] != s[i]&&j!=0)
            {
                j = prefix[j-1];
                
            }
            if(s[j] == s[i]){
                prefix[i] = prefix[j]+1; 
                j++;
            }
        }
            
    }
    return prefix;
    

    }
    class Solution {
    public:
    int strStr(string haystack, string needle) {
    if(needle.length()==0)
    return 0;

       vector <int> vec=prefix(needle);
      /* for(vector<int>:: iterator it = vec.begin(); it!=vec.end(); it++ )
        {
            cout<<*it<<endl;
        }*/
        int j=0,i=0;
        for( i=0; i<haystack.length();)
        {
            
            if(haystack[i]==needle[j])
                {
                    i++;    j++;
                }
            else{while(haystack[i]!=needle[j] && j!=0)
            {
                j=vec[j-1];
            }
            if(haystack[i]==needle[j])
                continue;
            else i++;}
           // cout<<i<<" "<<j<<endl;
        if(j==needle.length())  return i-j;
        }
        return -1;
    }
    

    };


Log in to reply
 

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