1. public static int strStr(String ss, String pp) {
    2.         if (pp.isEmpty()) return 0;
    4.         // 分别读取原串和匹配串的长度
    5.         int n = ss.length(), m = pp.length();
    6.         // 原串和匹配串前面都加空格，使其下标从 1 开始
    7.         ss = " " + ss;
    8.         pp = " " + pp;
    10.         char[] s = ss.toCharArray();
    11.         char[] p = pp.toCharArray();
    13.         // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相关的）
    14.         int[] next = new int[m + 1];
    15.         // 构造过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【构造 i 从 2 开始】
    16.         for (int i = 2, j = 0; i <= m; i++) {
    17.             // 匹配不成功的话，j = next(j)
    18.             while (j > 0 && p[i] != p[j + 1]) j = next[j];
    19.             // 匹配成功的话，先让 j++
    20.             if (p[i] == p[j + 1]) j++;
    21.             // 更新 next[i]，结束本次循环，i++
    22.             next[i] = j;
    23.         }
    25.         // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】
    26.         for (int i = 1, j = 0; i <= n; i++) {
    27.             // 匹配不成功 j = next(j)
    28.             while (j > 0 && s[i] != p[j + 1]) j = next[j];
    29.             // 匹配成功的话，先让 j++，结束本次循环后 i++
    30.             if (s[i] == p[j + 1]) j++;
    31.             // 整一段匹配成功，直接返回下标
    32.             if (j == m) return i - m;
    33.         }
    35.         return -1;
    36.     }