Shortest KMP code


  • 1
    Z
    class Solution {
      public:
         int strStr(char *haystack, char *needle) {
             int Hlen = strlen(haystack), Nlen = strlen(needle), k=-1, j=0, i=0, *prev = new int[Nlen];
             prev[0]=-1;
             while(j < Nlen-1){
                if( k==-1 || needle[k]==needle[j] ){
                     prev[++j] = ++k;   
                }else{
                     k = prev[k];
                }
            }
             i=j=0;
             while(i<Hlen&&j<Nlen){
                if(j==-1||haystack[i]==needle[j]){
                       i++;j++;
                }else{
                            j=prev[j];
                        }
                }
                if(j==Nlen){
                    return i - j;
                }else{
                     return -1;
                }
          }
    };
    

    This is my AC code for implementing Strstr()


  • 0
    Z

    would you mind tell me the time cost?
    I want to compare with my solution,thank you.


Log in to reply
 

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