关于字符串: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);