content: package question0028_implement_strstr;
  
  /**
   * https://leetcode-cn.com/problems/implement-strstr/
   *
   * KMP算法。
   *
   * 时间复杂度是O(n1 + n2)，其中n1为字符串haystack的长度，n2为字符串needle的长度。空间复杂度是O(n2)。
   *
   * 执行用时；11ms，击败12.12%。消耗内存：36.8MB，击败76.60%。
   */
  public class Solution2 {
      public int strStr(String haystack, String needle) {
          int n2;
          if (null == needle || (n2 = needle.length()) == 0) {
              return 0;
          }
          int n1;
          if (null == haystack || (n1 = haystack.length()) == 0) {
              return -1;
          }
          int[] next = getNext(needle);
          int j = -1;
          for (int i = 0; i < n1; i++) {
              while (j != -1 && haystack.charAt(i) != needle.charAt(j + 1)) {
                  j = next[j];
              }
              if (haystack.charAt(i) == needle.charAt(j + 1)) {
                  j++;
              }
              if (j == n2 - 1) {
                  return i - j;
              }
          }
          return -1;
      }
  
      private int[] getNext(String p) {
          int n = p.length(), j = -1;
          int[] next = new int[n];
          next[0] = -1;
          for (int i = 1; i < n; i++) {
              while (j != -1 && p.charAt(i) != p.charAt(j + 1)) {
                  j = next[j];
              }
              if (p.charAt(i) == p.charAt(j + 1)) {
                  j++;
              }
              next[i] = j;
          }
          return next;
      }
  }