old_contents: # Time:  O(n + m)
  # Space: O(m)
  #
  # Implement strStr().
  # 
  # Returns a pointer to the first occurrence of needle in haystack,
  #  or null if needle is not part of haystack.
  #
  
  # Wiki of KMP algorithm:
  # http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  class Solution:
      # @param haystack, a string
      # @param needle, a string
      # @return a string or None
      def strStr(self, haystack, needle):
          if not needle:
              return 0
              
          if len(haystack) < len(needle):
              return -1
          
          i = self.KMP(haystack, needle)
          if i > -1:
              return i
          else:
              return -1
      
      def KMP(self, text, pattern):
          prefix = self.getPrefix(pattern)
          j = -1
          for i in xrange(len(text)):
              while j > -1 and pattern[j + 1] != text[i]:
                  j = prefix[j]
              if pattern[j + 1] == text[i]:
                  j += 1
              if j == len(pattern) - 1:
                  return i - j
          return -1
      
      def getPrefix(self, pattern):
          prefix = [-1] * len(pattern)
          j = -1
          for i in xrange(1, len(pattern)):
              while j > -1 and pattern[j + 1] != pattern[i]:
                  j = prefix[j]
              if pattern[j + 1] == pattern[i]:
                  j += 1
              prefix[i] = j
          return prefix
      
  # Time:  (n * m)
  # Space: (1)
  class Solution2:
      # @param haystack, a string
      # @param needle, a string
      # @return a string or None
      def strStr(self, haystack, needle):
          for i in xrange(len(haystack) - len(needle) + 1):
              if haystack[i : i + len(needle)] == needle:
                  return haystack[i:]
          return None
      
  if __name__ == "__main__":
      print Solution().strStr("a", "")
      print Solution().strStr("abababcdab", "ababcdx")
  
new_contents: # Time:  O(n + m)
  # Space: O(m)
  #
  # Implement strStr().
  # 
  # Returns a pointer to the first occurrence of needle in haystack,
  #  or null if needle is not part of haystack.
  #
  
  # Wiki of KMP algorithm:
  # http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm
  class Solution(object):
      def strStr(self, haystack, needle):
          """
          :type haystack: str
          :type needle: str
          :rtype: int
          """
          if not needle:
              return 0
              
          if len(haystack) >= len(needle):
              return self.KMP(haystack, needle)
          return -1
      
      def KMP(self, text, pattern):
          prefix = self.getPrefix(pattern)
          j = -1
          for i in xrange(len(text)):
              while j > -1 and pattern[j + 1] != text[i]:
                  j = prefix[j]
              if pattern[j + 1] == text[i]:
                  j += 1
              if j == len(pattern) - 1:
                  return i - j
          return -1
      
      def getPrefix(self, pattern):
          prefix = [-1] * len(pattern)
          j = -1
          for i in xrange(1, len(pattern)):
              while j > -1 and pattern[j + 1] != pattern[i]:
                  j = prefix[j]
              if pattern[j + 1] == pattern[i]:
                  j += 1
              prefix[i] = j
          return prefix
      
  # Time:  (n * m)
  # Space: (1)
  class Solution2:
      # @param haystack, a string
      # @param needle, a string
      # @return a string or None
      def strStr(self, haystack, needle):
          for i in xrange(len(haystack) - len(needle) + 1):
              if haystack[i : i + len(needle)] == needle:
                  return haystack[i:]
          return None
      
  if __name__ == "__main__":
      print Solution().strStr("a", "")
      print Solution().strStr("abababcdab", "ababcdx")
  
subject: Update implement-strstr.py