0%

关于KMP算法中的一个小问题

最近看了一个算法,KMP,字符串查询算法,这个方法有各种各样的讲解,我个人最喜欢的还是在 《算法》 中所提到的用DFA的方式去解答这个算法。

算法的核心可以看这篇文章:

问题

关于其中一个小问题,我想仔细的聊一聊(如果没有看前面,请看下上文)。
这个问题就是关于DFA这个二维数组构建的时候,其中有一个变量X是什么?

1
2
3
copy  dfa[][X] to  dfa[][j]
dfa[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];

探寻

** 我们要明白X就是当前回退的状态 **

Step 0:

第一步构造,我们发现 我们现在所在的状态,能够回退的只有状态 0,而只有输入A的时候
我们才能进入1状态,这个没什么好说的。

1
2
3
4
5
6
7
8
  X (这是在初始化之后赋值的)

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1
B 0
C 0

Step 2:

第二步构造,我们首先确认,我们发现我们回退的状态是 0,那我怎么确定,我们所能回退的状态,这个时候X的作用出来了,X = 0这个时候,因为我们这个时候输入所有的,都是从0 开始回退的。

  • copy dfa[][X] to dfa[][j] , 这里其实就是匹配失败,我们发现,在第二次 匹配B的时候
    如果我们匹配的是A,我们是的确回到1状态就是 0 状态那一列,但是问题来了,这是我们自己想出来的,从DFA怎么看出来的,一开始我们所能回退的状态对于任何输入来说都是从 上一次的状态开始 开始,那我们这一次能够回退的就是 0 状态,就是所谓 状态为0的那一列。 换言之,我们这次输入如果不成功,那我们所有的输入都是从新开始计算的,那从新计算是不是状态0+某个数据 = 新状态,而这个新状态就是 0 状态那一列?

上面可能看不懂 其实就是假设,1 -> 2 状态转换的时候,我们失败了,那我们需要从哪里开始重新计算,那很简单,因为我们才 1 -> 2 状态,那我们只能从 0 -> 1重新计算。你 0 -> 1 状态的变化,是不是 J = 0 的那一列?

1
2
3
4
5
6
7
8
  X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1
B 0 0
C 0 0
  • dfa[pat.charAt(j)][j] = j+1; 这里很简单,就是如果是正确输入的字符串,我们的状态应该是当前输入状态+1.
1
2
3
4
5
6
7
8
  X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1
B 0 2
C 0 0
  • X = dfa[pat.charAt(j)][X] 这里为什么要升级X,原因是因为我们需要知道B这次是不是部份匹配上了,这一次 X = dfa[pat.charAt(j)][X] 带入参数,我们发现是 X = dfa[B][0], 这里就是以B为输入量,状态为 0 的时候,转换成了对象的状态, X= 0, 但是这个 0 和上次的 0 不是一个含义,这个 0 的含义是,这次输入B,所能从0状态转换成的状态也是0!
1
2
3
4
5
6
7
8
  X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1
B 0 2
C 0 0

Step 3:

  • copy dfa[][X] to dfa[][j]
  • dfa[pat.charAt(j)][j] = j+1
1
2
3
4
5
6
7
8
  X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3
B 0 2 0
C 0 0 0
  • X = dfa[pat.charAt(j)][X] 重点看这个问题,这个时候,我们看见我们的表格还是如上图。这个时候 X = dfa[A][0], X = 1, 为什么这里是 1,这个问题很和谐,其实这里的含义是,我们之前所能回退的状态都是0,而这一次我们输入的是 A,那在0状态输入A状态会变成什么?,当然是变成1状态。好,这个X我们保存。所以X = 1
1
2
3
4
5
6
7
8
    X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3
B 0 2 0
C 0 0 0

Step 4:

1
2
3
4
5
6
7
8
      X

J 0 1 2 3 4 5
A B A B A C
¯¯¯¯¯¯¯¯¯¯¯¯¯¯
A 1 1 3 1
B 0 2 0 4
C 0 0 0 0

这里哦我们就发现了,其实这里我们 copy dfa[][X] to dfa[][j] 的时候,我们是考虑匹配失败的时候,因为之前上一次的A,已经保证我们的状态会在1上,我们只需要从 1状态上把失败的状态Copy过来,更新成功的对象,在更新X就可以了。

总结

本篇是关于KMP的基于DFA状态机的理解,至于在算导中的next数组,还没有看各位看官还望斧正。

来杯奶茶, 嗝~~~