Implement with c++ KMP algorithm.


  • 0
    class Solution {
    public:
      int strStr(string haystack, string needle) {
        int j = 0;
        vector<int> next(needle.size());
    
        if ((haystack.size() == 0 && needle.size() == 0) || needle.size() == 0)
        {
          return 0;
        }  
        buildNextTable(needle, next);
        for (int i = 0; i < haystack.size(); i ++)
        {
          while (j > 0 && haystack[i] != needle[j])
          {
    	j = next[j - 1];
          }
          if (haystack[i] == needle[j])
          {
    	j ++;
          }
          else
          {
    	j = 0;
          }
    
          if (j == needle.size())
          {
    	return i - j + 1;
          }
        }
        return -1;
      }
    
      /**
       * @brief Build next table.
       *        Next table is longest prefix and suffix length of each index.
       */
      void buildNextTable(string needle, vector<int> &next)
      {
        next[0] = 0;
        for (int i = 1; i < needle.size(); i ++)
        {
          int tmp = next[i - 1];
          while (tmp && needle[tmp] != needle[i])
          {
    	tmp = next[tmp - 1];
          }
          if (needle[tmp] == needle[i])
          {
    	next[i] = tmp + 1;
          }
          else
          {
    	next[i] = 0;
          }
        }
      }  
    };
    

Log in to reply
 

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