文章分类 » 算法

KMP next数组讲解

本文只讲解KMP子串keyString(下标用j表示),中和源字符串SoureceString(下标i表示)某次匹配失败后。下次匹配j的取值。
关于KMP算法入门可以看看其他博文(最主要网上关于这个算法写烂了,我这里只记录下我学习不懂的地方)

前言

在学KMP算法的时候一直感觉next数组的实现是让我最头痛的。所以现在回过头写下笔记,方便以后再看。

规则:
1. keyString(子串)的next数组大小为keyString的长度。
2. next第一个元素为-1
3. next数组下标数等于 子串前缀和后缀的匹配数

前缀概念:
子字符串的从第一个元素开始到第x元素 和 字符第y个元素到最后一个字符串相等.(x和y可以相等)

注意 后缀的概念:有个误区 是指子字符串第z个元素的时候 把z最为最后一个元素

eg:
字符串 keyString =“abcabcx”

这里写图片描述

我们可以把.下标为1的元素(即是第二个元素)作为后缀。那么前缀是a。后缀是b
我们把下标为5的元素作为后缀。那么前缀是abc(下标为0,1,2)后缀是abc(下标为 3,4,5)

上面对应next数组
这里写图片描述
当子串到下标为6的位置和源字符串匹配失败的时候,下次匹配直接到下标为3的位置

ok 现在我们开始现实某个字符串next数组的实现,首先写一个方法为get

    //java语言
    // T为子字符串
    // next数组 
    // 当方法结束的时候 next包含对应T的射影数值
    public static void get(String T, int[] next) {
    ....
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

我们先实现前两个规则

规则:
1. keyString(子串)的next数组大小为keyString的长度。
2.  next第一个元素为-1
  • 1
  • 2
  • 3

如下

//默认传入的next数组大小为子字符串大小 所以实现规则2即可
public static void get(String T, int[] next) {

        int i, j;

        j = -1;
        next[0] = -1;
        i = 0;

    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

最后一个规则:

next数组下标数等于 子串前缀和后缀的匹配数.先看一下next完成的案例在说

算法核心也在这此处,再回头看看如下字符串和对应next数组
这里写图片描述

理解next数组的含义
我们看一下‘x’对应next为6
意味着:
1. 字符串从0到5作为前缀。(为什么不到6?因为数组下标从0开始)
2. 从x下标减6开始到x前面一个数作为后缀。
3. 有6个循环数。
这里写图片描述

先看最终代码(可能会疑惑在回溯部分,先暂时看看后面再解释):

 public static void get(String T, int[] next) {

        int i, j;

        j = -1;
        next[0] = -1;
        i = 0;
        while (i < T.length() - 1) {

            if (j == -1 || T.charAt(i) == T.charAt(j)) {

                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];//回溯
            }
        }
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19

关于回溯我们举例说明说明

我们假设数组末尾追加一个字母d(下标为10)

这里写图片描述

假设我们的算法遍历到下标为10 数值为x的元素。
此时

j=6. i = 9
  • 1

此时算法 T.chatAt(i) 不等 T.chatAt(j)所以走else路径

 j = next[j];//回溯
  • 1
  • 将j回溯到next[6]的位置,如果此时相等那么 即T.chatAt(i)== T.chatAt(j)。那么就结束了。不然继续回溯。我当时在想为什么j会回溯到next[j]。原因如下,j代表着有多少个后缀和前缀数相等的数量。那么我们将设 下标为10(数值x)的元素等于下标为6(数值a)的元素 。循环到此的时候j=6代表着在下标为9的元素之前有6个相等数。(0,1,2,3,4,5 和 3,4,5,6,7,8)。那么6 和 9 相等就代表着相同后缀有6个。所以我们只需要判断字符串6和9即可(因为此算法如果前面的数字前缀相等那么会建立再次基础上 进行判断【j= 6 就是一个基础,它代表着 前缀的后面一个数 也代表着前缀和后缀相同数】)。

  • 那么假设不相等的情况的解释:
    继续假设运行到
    我们的算法遍历到下标为10 数值为x的元素。
    此时

j=6. i = 9
  • 1

(0,1,2,3,4,5 和 3,4,5,6,7,8前面判断已经相等),但是数组下标6和9不相等 进行j回溯到next[6]的位置,也就是 j = 3 的位置( next[6] = 3),
j代表某前缀的最后一个数的后面一个数。比如说 j =3 那么前缀就是 0 1 2。我们在我们 j =6 i =9 匹配失败后 你可以让 j = j-1继续匹配 T.chatAt(9),但是这是多余的。

假设 数组下标6 和9 匹配失败 进行 j=j-1
T.chatAt(6) != T.chatAt(9);
j = j-1 = 5;
那么
T.chatAt(5) == T.chatAt(9);
也就是if判断条件成立 可得
0 1 2 3 4 5 和 4 5 6 7 8 9相等.
那么可以得以下结论:
T.chatAt(5) == T.chatAt(9);
T.chatAt(5) == T.chatAt(8);
T.chatAt(8) == T.chatAt(9);
这三个不难推理出

继续
T.chatAt(4) == T.chatAt(8);
T.chatAt(9) == T.chatAt(4);
T.chatAt(9) == T.chatAt(5);

也就是 7==8==9 和 1==2==3

最终你将推出 0==1==2==3==4==5 ==7==8==9
显然这会和next数组原有数组数值发生冲突。顾不能直接j= j-1。当然如果数组前缀和后缀所有元素都相等 时候可以推出next[j] = j -1