题目

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

暴力破解

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

 1/**
 2 * 暴力破解
 3 *
 4 * @param s s为被匹配字符串 babababcbabababb
 5 * @param p p为匹配字符串   bababb
 6 */
 7private static int indexOf(String s, String p) {
 8    // i 指针指向s字符串,即匹配字符串的起始下标
 9    int i = 0;
10    // sc 指针指向s字符串
11    int sc = i;
12    // j 指针指向p字符串
13    int j = 0;
14    // 当 sc 指向 s 的末尾时结束循环
15    while (sc < s.length()) {
16        // 如果 sc 和 j 指向字符串的字符相同,则指针向后移动
17        if (s.charAt(sc) == p.charAt(j)) {
18            sc++;
19            j++;
20            // 当指针 j 指向 p 字符串末尾时,表示字符串匹配,结束方法
21            if (j == p.length()) {
22                return i;
23            }
24        } else {
25            // 如果不相同,则移动i指针,其他指针恢复默认值
26            i++;
27            sc = i;
28            j = 0;
29        }
30    }
31    return -1;
32}

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 数组的代码实现:

 1private static int[] next(String ps) {
 2    int length = ps.length();
 3    int[] next = new int[length];
 4    char[] p = ps.toCharArray();
 5    next[0] = -1;
 6    if (ps.length() == 1) {
 7        return next;
 8    }
 9    next[1] = 0;
10    int j = 1;
11    // 确定位置j的最长匹配前缀在那哪里
12    int k = next[j];
13    while (j < length - 1) {
14        // 现在要推出next[j+1],检查j和k位置上的关系即可
15        if (k < 0 || p[j] == p[k]) {
16            next[++j] = ++k;
17        } else {
18            k = next[k];
19        }
20    }
21    return next;
22}
KMP 的代码实现

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

 1private static int indexOf(String s, String p) {
 2    // i 指向s字符串
 3    int i = 0;
 4    // j 为指向p字符串
 5    int j = 0;
 6    // 求得 next 数组
 7    int[] next = next(p);
 8    // 当 i 指向 s 的末尾时结束循环
 9    while (i < s.length()) {
10        // 如果 i 和 j 指向字符串的字符相同,则指针向后移动
11        if (j == -1 || s.charAt(i) == p.charAt(j)) {
12            i++;
13            j++;
14        } else {
15            // j 根据 next 数组回溯到指定下标
16            j = next[j];
17        }
18        // 当指针 j 指向 p 字符串末尾时,表示字符串匹配,结束方法
19        if (j == p.length()) {
20            return i-j;
21        }
22    }
23    return -1;
24}

标题:字符串匹配——KMP
作者:Yi-Xing
地址:http://zyxwmj.top/articles/2020/05/06/1588757132090.html
博客中若有不恰当的地方,请您一定要告诉我。前路崎岖,望我们可以互相帮助,并肩前行!