关于字符串:KMP算法

在利用中常常会遇到字符串比拟的算法，判断一个字符串pp是否是另外一个字符串ss的子串。
注明的算法是KMP算法，当初整顿如下，参考 宫水三叶 的代码实现。

// 作者 宫水三叶// 链接 https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/// KMP 算法// ss: 原串(string)  pp: 匹配串(pattern)// 工夫复杂度O(m + n)public int kmp(String ss, String pp) {    if (pp.isEmpty()){        return 0;    }    // 别离读取原串和匹配串的长度    int n = ss.length(), m = pp.length();    // 原串和匹配串后面都加空格，使其下标从 1 开始    ss = " " + ss;    pp = " " + pp;    char[] s = ss.toCharArray();    char[] p = pp.toCharArray();    // 构建 next 数组，数组长度为匹配串的长度（next 数组是和匹配串相干的）    int[] next = new int[m + 1];    // 结构过程 i = 2，j = 0 开始，i 小于等于匹配串长度 【结构 i 从 2 开始】    for (int i = 2, j = 0; i <= m; i++) {        // 匹配不胜利的话，j = next(j)        while (j > 0 && p[i] != p[j + 1]){            j = next[j];        }        // 匹配胜利的话，先让 j++        if (p[i] == p[j + 1]){            j++;        }        // 更新 next[i]，完结本次循环，i++        next[i] = j;    }    // 匹配过程，i = 1，j = 0 开始，i 小于等于原串长度 【匹配 i 从 1 开始】    for (int i = 1, j = 0; i <= n; i++) {        // 匹配不胜利 j = next(j)        while (j > 0 && s[i] != p[j + 1]){            j = next[j];        }        // 匹配胜利的话，先让 j++，完结本次循环后 i++        if (s[i] == p[j + 1]){            j++;        }        // 整一段匹配胜利，间接返回下标        if (j == m){            return i - m;        }    }    return -1;}

如果是java的开发者，能够应用jdk自带的

// 工夫复杂度O(m * n)ss.indexOf(pp);