题目

  查找字符串 s2 在字符串 s1 的位置,如果存在则返回起始下标,不存在则返回 -1。

暴力破解

  我们使用指针的方式对字符串的每个字符进行比较。

/**
 * 暴力破解
 *
 * @param s s为被匹配字符串 babababcbabababb
 * @param p p为匹配字符串   bababb
 */
private static int indexOf(String s, String p) {
    // i 指针指向s字符串,即匹配字符串的起始下标
    int i = 0;
    // sc 指针指向s字符串
    int sc = i;
    // j 指针指向p字符串
    int j = 0;
    // 当 sc 指向 s 的末尾时结束循环
    while (sc < s.length()) {
        // 如果 sc 和 j 指向字符串的字符相同,则指针向后移动
        if (s.charAt(sc) == p.charAt(j)) {
            sc++;
            j++;
            // 当指针 j 指向 p 字符串末尾时,表示字符串匹配,结束方法
            if (j == p.length()) {
                return i;
            }
        } else {
            // 如果不相同,则移动i指针,其他指针恢复默认值
            i++;
            sc = i;
            j = 0;
        }
    }
    return -1;
}

KMP

  所谓 KMP 就是在指针暴力破解的基础上,引入 next 数组,来确定每次 j 指针回溯的位置(而不是每次都回溯到 0),从而提高效率。

next 数组

  next 数组中储存的是字符串中前缀和后缀相同字符串的最长长度,在字符匹配时,失配后其中的值决定指针回退的位置。

求 next 数组的方法

  求字符串的 next 数组方法,先将字符串拆分成字节数组 p ,并定义 j 指针指向 next 数组的下标(指向 下标 1,0 下标为 -1),然后定义 k 指针指向最长匹配前缀的下标(默认为 0)。如果 p[j]==p[k] 或 k<0,则 next(++j)=++k ;否则,k 回溯(k = next[k]),直到 j < length - 1。
  我们可以确定 next 数组的第一个元素值为 -1,因而可以得到第二个元素值为 0,后面的根据公式进行推导。假如:s 字符串为 babababcbabababb,p 字符串为 bababb。首先列出 p 字符串的所有前缀,如图:(next[3] 存储的是 bab 前缀和后缀相同字符串的最长长度,所以为 1,依次类推)

next1.png

  求 next 数组的代码实现:

private static int[] next(String ps) {
    int length = ps.length();
    int[] next = new int[length];
    char[] p = ps.toCharArray();
    next[0] = -1;
    if (ps.length() == 1) {
        return next;
    }
    next[1] = 0;
    int j = 1;
    // 确定位置j的最长匹配前缀在那哪里
    int k = next[j];
    while (j < length - 1) {
        // 现在要推出next[j+1],检查j和k位置上的关系即可
        if (k < 0 || p[j] == p[k]) {
            next[++j] = ++k;
        } else {
            k = next[k];
        }
    }
    return next;
}
KMP 的代码实现

  在指针暴力破解的基础上,引入 next 数组,来确定每次 j 指针回溯的位置,时间复杂度为 O(n+m)。

private static int indexOf(String s, String p) {
    // i 指向s字符串
    int i = 0;
    // j 为指向p字符串
    int j = 0;
    // 求得 next 数组
    int[] next = next(p);
    // 当 i 指向 s 的末尾时结束循环
    while (i < s.length()) {
        // 如果 i 和 j 指向字符串的字符相同,则指针向后移动
        if (j == -1 || s.charAt(i) == p.charAt(j)) {
            i++;
            j++;
        } else {
            // j 根据 next 数组回溯到指定下标
            j = next[j];
        }
        // 当指针 j 指向 p 字符串末尾时,表示字符串匹配,结束方法
        if (j == p.length()) {
            return i-j;
        }
    }
    return -1;
}

标题:字符串匹配——KMP
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/05/06/1588757132090.html
版权声明:本文为博主原创文章,转载请附上博文链接!
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!

添加新评论