再论KMP的NFA数组

2022-02-17  本文已影响0人  西部小笼包

在我20年写的这篇文章里，已经把DFA给讲的比较透彻了。但重读了一下NFA的部分，还是有些瑕疵。打算这次希望把它讲透，下次再理解KMP的NFA解法时（又称next数组解，或不确定有限状态机解），可以一目了然。

行文的用词

  1. 待匹配的文本为str（string的缩写）
  2. 要匹配的串为pat(pattern的缩写),

step1. nfa 数组的定义

KMP-NFA解的第一步就是构建NFA（NEXT）数组

int[] nfa = new int[pat.length];

这个数组的作用是 当pat[j] ！= str[i] 的时候，nfa[j]存的是我们下一个值得一试的J的位置在哪？

如果是确定状态机，我能明确知道 J 该变到什么位置（一次成功）；但是再非确定的状态机下，我能明确知道这个J是值得一试的（当次可能成功可能失败，需要试多次）
如果感兴趣KMP的确定状态机是怎么实现的，可以看我上面提供的那个链接，20年写的那篇博客

如下图的红色框：

image.png
长串的C 和 匹配串的最后一个D 失配了，也就是我们之前 说的pat[j] ！= str[i] 的时候；可以看到当时J = 6, nfa[6] = 2; 为2的原因也就是图中的蓝色框。带匹配文本的索引I之前的后缀AB，等于匹配串的前缀AB;
所以如果我们把NFA数组的每个数字都左移1格，也就是nfa[i - 1] = nfa[i], 那存的就是最长的公共前后缀(缩写为lcx)。

比如

pat[]: A B C D A B
lcx[]: 0 0 0 0 1 2
nfa[]:-1 0 0 0 0 1 2

上面NFA，是不带优化的NFA。也就是在STEP 3时，即使字符相同，也去试一下。有时为了构建最长公共前后缀数组，会不做step3的那个优化；

step2. nfa 数组的初始化

int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
  // 下面是进入循环必须要符合的不变量（如果不变量不成立，则算法有BUG）
  assert pat.substring(0, j).equals(pat.substring(i - j, i));
  for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
}

nfa[0] = -1 因为如果待匹配的字符串第一个字符，和当前文本的字符就不一致。那么直接可以i++, j++; 看文本下一个字符是否能和待匹配的字符串第一个字符去匹配了。所以根据上一步的NFA的定义，J应该是-1;

其实我们也可以把-1的位置理解为正则的*, 一个万能字符

既然0的值很清楚了。下面我们的目标就是要把 NFA 数组的 从1到NFA.LENGTH -1 的值给确定出来。
所以有 for (int i = 1; i < nfa.length; i++)
那么I也就定义明白了。
为了给NFA赋值，我们需要另外一个指针J。这个J的作用正如我们上面提到的，逻辑链路是这样的。

  1. NFA[I] 是在失配（下图红框）时，下一个值得尝试的位置。
  2. 下一个值得尝试的位置，必然是在pat[0:i-1]里存在一个最大的J，使得pat[0:j) == pat[i - 1 - j:i) (注意[x,y)表示前闭后开区间）。这个等式，就是下图蓝框。
    image.png
  3. 那么我们就需要一个变量来存这个J。有了J我们就可以很依靠这个J去构建NFA

要验证的不变量

上面我们讲清楚了I和J的意义，也非常好理解进入循环开始时，我们要验证的不变量。注意JAVA里的substring(x,y)表示前闭后开区间！

  1. assert pat.substring(0, j).equals(pat.substring(i - j, i)); 表示满足前后缀相等
  2. for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i)); 表示J是满足前后缀相等这个条件里，在[0,i-1]这个范围里最大的

那么在 I = 1的情况下，J的初始值只能为0. 来满足上面的不变量。

step3. 给NFA赋值

既然，我们进入循环内，满足上面的2个不变量条件。
那么J 其实就是NFA[I]的值了。

int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
  // 下面是进入循环必须要符合的不变量（如果不变量不成立，则算法有BUG）
  assert pat.substring(0, j).equals(pat.substring(i - j, i));
  for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
  nfa[i] = j;
}

如果需要求得最长公共前后缀数组，则不能用下面的优化；上面的代码也是WORK的，就是效率会低一点。

当然这么写是没有问题的，但是破坏了一个我们之前对NFA数组的一个定义，就是存的是值得一试的J。
想一下我们的 PAT[I] 如果和 STR[K] 已经匹配失败了str[k] != pat[i]。 我们下一个值得试的位置是NFA[I]，如果pat[nfa[i]] == pat[i]，必然就会有 str[k] != pat[nfa[i]]; 那么我们其实可以保证我们NFA[I]里存的下一个位置J，这个J所在的字符和I所在的字符得不一样。这样这个J才能算值得尝试。（通过I就能知道的必败的J不值得一试）；所以正确的代码如下:

int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
  // 下面是进入循环必须要符合的不变量（如果不变量不成立，则算法有BUG）
  assert pat.substring(0, j).equals(pat.substring(i - j, i));
  for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
  nfa[i] = pat[i] != pat[j] ? j : nfa[j];
}

虽然J满足2个不变量，但是因为pat[i] == pat[j],，J依赖不值得一试，所以不能写进NFA[I]里

既然NFA里要求存的是值得一试的J，NFA[I]要存的是在根据当前的J的位置去NFA里找下一个值得一试的J，也就是NFA[J]。

举个例子：
虽然红框的第三行，也满足2个不变量，但是因为红框右侧都是D，所以不值得一试，不如直接选择满足不变量1的但是字符不同的蓝色框第四行去尝试，来的高效


1645111473(1).png

因为是从NFA里取出来的，必然满足pat[i] != pat[nfa[j]], 如果找不到这样的nfa[j]，nfa[j]里也会存着-1来兜底。
比如 aa 的 nfa数组 就是 [-1, -1]

step4. 更新J用来保护下一个循环不变量不被破坏

这个NFA[I] 搞定之后，迎接我们的就是下一轮循环，I 会+1；所以我们必须要在进入下一个循环前，去更新J以满足下一个循环下和I+1合作的时候，不变量不被破坏。

情况1 pat[i] == pat[j]

这个时候因为前面的不变量有 assert pat.substring(0, j).equals(pat.substring(i - j, i));
那么即使I++, J++后，这个不变量依然存在因为 pat.substring(0, j+1).equals(pat.substring(i - j, i+1))

情况2 pat[i] ！= pat[j]

如下图P[J] != P[K] (P数组含义等价于PAT数组，只是不同叫法)

image.png
我们应该让K = NEXT[K] (next数组和NFA数组是一个意思,为了配合图片用NEXT数组表述这段）；因为NFA的定义P[k] != P[next[k]]
所以就有可能使得P[next[k]] == P[J] ，如果还失败了，就继续用NEXT数组找下一个，一直会到-1去兜底。
因为走的是NEXT数组，一旦相同了，公共前后缀的性质必定满足。那么前缀和后缀都同时加上一个同样的字符，那么必定还是满足公共前后缀性质。因为J是单调递减的，J > NFA[J] > NFA[NFA[J]] ; 所以最大的J这个性质也可以满足。
通过上面的方法，我们就知道如何维护J了。也就得出KMP 构建NFA数组的全部代码 
int[] nfa = new int[pat.length()];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++) {
  // 下面是进入循环必须要符合的不变量（如果不变量不成立，则算法有BUG）
  assert pat.substring(0, j).equals(pat.substring(i - j, i));
  for (int k = j + 1; k < i; k++) assert !pat.substring(0, k).equals(pat.substring(i - k, i));
  nfa[i] = pat[i] != pat[j] ? j : nfa[j];
  while (j >= 0 && pat[i] != pat[j]) j = nfa[j];
  j++;
}

step5. 使用NFA

leetcode 28题
https://leetcode.com/problems/implement-strstr/

public int strStr(String strr, String patt) {
        char[] str = strr.toCharArray(), pat = patt.toCharArray();
        int[] nfa = new int[pat.length];
        if (nfa.length == 0) return 0;
        nfa[0] = -1;
        for (int i = 1, j = 0; i < nfa.length; i++, j++) {
          // 下面是进入循环必须要符合的不变量（如果不变量不成立，则算法有BUG）
            assert patt.substring(0, j).equals(patt.substring(i - j, i));
            for (int k = j + 1; k < i; k++) 
                assert !patt.substring(0, k).equals(patt.substring(i - k, i));
          // 不变量验证结束，不变量验证的代码可在测试后，注释掉
            nfa[i] = pat[i] != pat[j] ? j : nfa[j];
            while (j >= 0 && pat[i] != pat[j]) j = nfa[j];
        }
        // 下面是NFA数组的使用部分
        int i = 0, j = 0;
        for (; i < str.length && j < pat.length; i++, j++) {
            while (j >= 0 && str[i] != pat[j]) j = nfa[j];
        }
        return j == pat.length ? i - j : -1;
    }
上一篇下一篇

猜你喜欢

热点阅读