字符串算法(1)-KMP, AC自动机

2020-07-19 本文已影响0人西部小笼包

现在写文章，也是痛点在哪，就写哪？今天的痛点是老是记不住KMP算法。
我曾经3次拿下KMP算法。但令人遗憾的是，我又忘记了。
所以决定还是写写，这样下次可以快速捡起来。网上有很多很好的KMP的学习材料。
一般都是从头讲起的。我这里推荐出来，给完全没接触过的KMP的小伙伴。
KMP超详细讲解
上面这篇文章应该是我看到的最好的讲解了。

我下面的讲解，是从另一个角度去思考KMP算法的。

KMP本身理解就比较复杂。如果我的讲解，你们看不懂，可以去看我上面分享的。

1. 直觉

在计算机的世界里数据都是以01形式表示。
比如有一串数据流是01110111101.
我们想在这串数据流中找到是否含有01111这个子串
那么在暴力做法时，我们匹配到第5个字符，发现失配了。
那么人的直觉就是因为要匹配的串开头是0. 一直匹配到第5个字符才不对，前面都对。那么必然为01110 所以我们可以直接把开头的0移动到失配的那个0上。
这样就可以提高匹配速度。

2. next array

lc 里有很多题目，都可以通过初始化一个NEXT ARRAY来提高算法的时间复杂度。
TODO: 之后会补充例子进来
NEXT ARRAY一般会去存，从这个位置开始包括这个位置下一个J字符的INDEX是什么，如果之后没有J字符了，那么就返回-1.
因为一般题目会说只有小写字母。所以我们可以用26 * N的时间，构造好这个NEXT ARRAY。之后就可以实现O(1)的跳跃。

// next array 构造法
char[] cs = str.toCharArray();
int l = cs.length;
int[][] next = new int[l + 1][26];
Arrays.fill(next[l], -1);
for (int i = l - 1; i >= 0; i--) {
    next[i] = next[i+1].clone();
    next[i][cs[i]-'a'] = i;
}

为什么可以这么构造？

核心就是从后往前，当前这个字符只会改变这层状态机的这个字符的状态点。其余的字符都是继承来自后面的状态机的转移。
如果后面有该字符（非本层字符），后一层的状态机已经掌握了最近的这个字符的下标的INDEX。所以我这层就可以直接用。
如果是本层字符，显然我自己最近。我就用我自己就好了。

那么如何使用NEXT ARRAY呢？

比如我们要找一个串是不是目标串的子序列。我们已经把目标串的NEXT ARRAY构建出来后。可以用如下代码快速判断。

int i = 0;
for (char c : cs) {
   i = next[i][c-'a'];
   if (i == -1) return false;
}
return true;

3. 有限确定状态机

其实上面的NEXT ARRAY 就是一种有限确定状态机。他定义了你在哪个INDEX i下状态为J.应该转移去哪个INDEX。
任何状态i, j 都对应1个确定性的去处。（只需查1次，就知道）
这个就是DFA， Deterministic finite state, 有限确定状态机的思想。
我们如果把这个思想引入到字符串匹配中，就是思考如何构造一个DFA，使得每一个状态都有对应的去处。
假设我们有了这个DFA数组，我们如何利用它快速匹配字符串呢

for (int i = 0, j = 0; j < dfa.length && i < cs.length; i++) {
    j = dfa[j][cs[i]-'a'];
}
if (j == dfa.length) return i - j; // dfa走到终态了
return -1;

那么我们就把找匹配字符串的时间复杂度从暴力的O (N ^ 2) 优化到了O (N)

下面就是如何去构造这个DFA。
其实思想也是和NEXT ARRAY 非常相似。也是分为2步。
大多数状态是继承上一层的，我这层只管正确的那个状态进行更新。
要更新的状态，其实就是模式串和查找串字符相等的时候，我们需要推进一格。

image.png

上图应该不难理解。
下面就是其他不匹配的状态是如何继承的呢？
我们可以知道当我们在第一个字符时，凡是不匹配的也只能回退到当前。因为已经退无可退。随后的不匹配是等价于用[1, k]的走状态机的模式的走到的串。

为什么这样是对的。举个例子我在匹配abc 到c 失败了，要回退的位置等价于用bc从头开始走状态机走到的位置。（因为暴力试错下，算法就是这么走的）

再比如如上图我用ABABC构建了DFA状态机。我查询串是ABABA.... 会发现走到第5个字符失配了。那么我可以用BABA去重走状态机，走到的位置等价于我在第5个位置失配要走到的位置是一样的。

image.png

有了这个观察之后，我们就知道我们需要维护2层状态，1层是用0...k，另一层就是用1....k 来表示上图的黑线的状态机。
那么我们在更新上图中J的状态机时，第一步继承的时候本质就是继承上一层黑线的A转移和B转移。然后更新自己的C转移
就可以写出构造DFA的方法了。

char[] cs = str.toCharArray();
int l = cs.length;
int[][] dfa = new int[l][26];
dfa[0][cs[0]-'a'] = 1; // 构建初始层
for (int i = 1, pre = 0; i < l;  pre = dfa[pre][cs[i] - 'a'], i++) {
    dfa[i] = dfa[pre].clone(); // 继承
    dfa[i][cs[i]-'a'] = i+1; // 更新自己
}

综上我们就介绍完了字符串匹配里的DFA的算法。
我希望你们可以理解基础的NEXT ARRAY，然后基于NEXT ARRAY的思想和字符串匹配的暴力解的性质，自己推导出DFA的算法。这样就不容易忘记了。即使忘记，也可以从NEXT ARRAY下手来回忆。

小伙伴可能会觉得和传统的KMP算法讲解完全不一样啊。
下面我们来回归到其他博客经常会介绍的KMP算法。

他的本质其实是不确定有限状态机的解法。又称NFA，Nondeterministic finite state
这个算法是实现正则表达式计算引擎的算法。有兴趣的小伙伴可以深入了解，他是怎么被运用在正则表达式解析总的。

因为如果想用DFA来构造所有的状态转换，状态数量（指数）过于庞大。是不可行的，所以引入的NFA。

4. NFA解法

在NFA解法里，当一个状态不匹配时，就可能需要多次跳跃。因为不能罗列所有不匹配的情况。所以只能在状态机里存可能是正确的解的情况。
那么这个状态机，我们定义为，nfa[i] 当查询串当前的索引J 和匹配串的I 不匹配时。匹配串可能和索引J匹配的位置在哪。
那么构建初始值必然是nfa[0] = -1，因为在初始位置不匹配，下一个无论如何回退都是无法匹配上的，就只能返回-1.
之后的NFA数组怎么构建，我们可以用2个视角去看。这样可以看的更清晰。

自底向上看

匹配串为char[] pat;，目标构建int[] nfa;
我们有了0，我们就要去看nfa[1]怎么构建？按照定义我们就需要判断pat[0]是否和pat[1]相等。如果相等, 那么其实如果发生了不匹配, nfa[1] = nfa[0]是一致的。我们把这个性质称作匹配可继承，意思就是如果2个字符一样，我就可以直接使用前一个的NFA转移来作为我自己的NFA转移。

如果不相等。因为当前pat[1]和一个字符不匹配了，那个字符是有可能和pat[0]匹配的。所以nfa[1] = 0即可。

当为2的时候，我们意识到要想继续用匹配可继承。所以之前的J往前回跳的字串，必须得让大号索引I 之前的字串都要有。这样才可以安全的去继承回跳状态。
那么我们就必须在处理2的问题前,要保证如果0和1的结尾字符不一样，就必须得把0调整为-1. 来确保，我们上面提到的性质。
那么总结出来，就是有2个指针，一个i指针依次取计算NFA[I]。另一个j指针，目标是使得pat.substring(0, j) == pat.substring(i - j, i)注意JAVA里SUBSTRING函数是前闭后开的。那么如果pat[j] == pat[i] i++, j++这个目标依然可以满足。
但是pat[j] ！= pat[i] 我们就必须调整J，让他能够继续满足pat.substring(0, j) == pat.substring(i - j, i)

在自底向上看的方法里，我们依赖2个串的前缀长度的字符完全一致。好直接继承使用之前算过的NFA来表达自己未知的NFA。其实图简单，只要我们每次把J设置成-1，这个条件就必然成立了。但是也就退化成了暴力解法。所以我们的目标是要找到尽可能大的J，满足pat.substring(0, j) == pat.substring(i - j, i)

所以在我们前一个定义上我们要加强一下
定义1： nfa[i] 当查询串当前的索引I 和匹配串的J 不匹配时。匹配串可能和索引I匹配的位置在哪。
定义2： 在众多的可能位置中，我们希望J 尽可能大

下面我们自顶向下看，如果调整J 使得可以找到最大的J

自顶向下看

我们构造一个全局的视角，假设有一个字符串。我们构造好了NFA。
当它失配的时候，我们必须要在NFA里找到下一个可能的位置去和当前失配的字符去比。如果成功，则可以继续往前走。
所以这就必须要求，这个可能的位置的前面如果有字符，那么它的所有字符，必然是当前这个查询串的后缀。我来画个图。

image.png

就是要求蓝色部分的相等是必须保证的。然后我来适配这个新过来的字符和当前失配的字符是否一致。

所以就有了下面这个图。

image.png
我们假设上面这个字符串0...j-1的NFA都构造好了。
因为在使用的时候如果J 失配了。nfa[j] 要回去的位置必然也是以蓝色区域为前缀的。不然就满足不了我们上面提到的性质。
所以我们在构造NFA[J]的时候，如果不相等，我们要安心的把nfa[j] = k的前提是
pat[nfa[k]] == pat[j] .
这样我们就保证了pat.substring(0, j) == pat.substring(i - j, i)这个不变量的同时，满足了前缀蓝色和后缀蓝色相同的性质。

综上我们可以得出如下代码。

char[] pat = pattern.toCharArray();
int[] nfa = new int[pat.length];
nfa[0] = -1;
for (int i = 1, j = 0; i < nfa.length; i++, j++) {
// 不变量 assert(pattern.substring(0, j).equals(pattern(i-j, i));
     nfa[i] = (pat[i] == pat[j] ? nfa[j] : j);
     while (j >= 0 && pat[j] != pat[i]) j = nfa[j];
}

有了NFA之后，在使用这个数组的时候，因为他是不确定的，所以我们可能要跳多次跳到匹配的字符。有如下代码：

for (int i = 0, j = 0; j < nfa.length && i < cs.length; i++, j++) {
    while (j >= 0 && pat[j] != cs[i]) j = nfa[j];
}
if (j == nfa.length) return i - j;
return -1;

这里我们在回望一下其他博客一般会介绍的NEXT数组的定义，其实就是从J失配，那么NEXT[J]存的就是从i开始的最大前缀长度能MATCH上pat[j]的后缀。其实是有共通性的。
我们不妨把文章开头推荐的博客最后的那个优化过的KMP NEXT ARRAY求法。换一种方法写出来。
有如下代码

char[] pat = pattern.toCharArray();
int[] next= new int[pat.length];
next[0] = -1;
int i = 0, j = -1;
while (i < next.length - 1) {
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    j++;
    i++;
    next[i] =  (pat[i] == pat[j] ? next[j] : j);
}

博客里原始的NEXT ARRAY的求法。（就是前缀后缀最长公共元素长度值向右移动一格的数组）. 因为有些题目我们是需要知道前缀后缀最长公共元素长度值，那么就可以用下述求法，因为向右移动了一格。所以我们可以补一个无用CHAR在最后。得到全部的前缀后缀最长公共元素长度值

char[] pat = pattern.toCharArray();
int[] next= new int[pat.length];
next[0] = -1;
int i = 0, j = -1;
while (i < next.length - 1) {
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    next[++i] =  ++j;
}

LC 里有很多题，是基于前缀后缀最长公共元素来解的。
比如

Shortest Palindrome
Repeated Substring Pattern
Longest Happy Prefix
大多数题解也解释的很清楚了，其实就是算出NEXT数组后，利用最大值可以直接或间接得到题目所求。

回到上面的代码，我们不难发现，J其实就是存在I里的。所以我们可以做进一步简化。

char[] pat = pattern.toCharArray();
next[0] = -1;
for (int i = 0; i < next.length - 1;) {
    int j = next[i];
    while (j >= 0 && pat[i] != pat[j]) j = next[j];
    next[++i] =  j + 1;
}

AC自动机

做这步简化，为的是引出我们的AC自动机的模板。下面每一行，都是一个等价。

KMP这个状态机转换，是在一个匹配串上。如果有一组匹配串，我们就会用到AC自动机。

我们用一个CHAR[] 来存一个匹配串。我们可以用一颗TRIE树来存一组匹配串。

当在TRIE树中搜索时，当一个节点发生了失配。在KMP中，我们用NEXT数组找到下一个可能匹配上的节点。在TRIE树中，我们对每个TRIE节点，都建立一个NEXT指针，表示失配的时候可以跳到哪个节点。

在计算NEXT数组时，我们是根据CHAR[]从前往后，后面的NEXT[I] 往往依赖于前面的NEXT[J]。

在AC自动机中，我们遍历的是TRIE树，下层的节点的NEXT指针依赖于之前层节点的NEXT指针。所以这里我们需要用BFS来BUILD AC自动机。

我们在初始化NEXT数组时，NEXT[0] = -1。我们假设TRIE树根节点为-1，之后第一层所有孩子的NEXT指针，都指向根节点。

AC自动机模板

public class ACTemplate {
    class Node {
        Node[] chds = new Node[26];
        Node next = null;
        // other value...
        boolean isWord = false;
    }
    // trie inser template
    void insert(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            int idx = c - 'a';
            if (p.chds[idx] == null) p.chds[idx] = new Node();
            p = p.chds[idx];
        }
        // update other value
        p.isWord = true;
    }
    Node root = new Node();
    void buildNextPointer() {
        Queue<Node> q = new LinkedList<>();
        // same as next[0] = -1;
        for (int i = 0; i < 26; i++) {
            if (root.chds[i] == null) continue;
            root.chds[i].next = root;
            q.offer(root.chds[i]);
        }
        while (!q.isEmpty()) {
            Node i = q.poll();
            for (int k = 0; k < 26; k++) {
                Node iPlusOne = i.chds[k]; // iPlusOne = i + 1 in kmp
                if (iPlusOne == null) continue;
                Node j = i.next;
               // same as while (j >= 0 && pat[i] != pat[j]) j = next[j];
                while (j != root && j.chds[k] == null) j = j.next; 
                iPlusOne.next = j.chds[k]; // same as next[i + 1] =  j + 1;
                if (iPlusOne.next == null) iPlusOne.next = root; // avoid NPE
                q.offer(iPlusOne); // for BFS
            }
        }
    }
    int query(String text) {
        char[] cs = text.toCharArray();
        Node j = root;
        int wordCnt = 0;
        for (int i = 0; i < cs.length; i++) {
            int idx = cs[i] - 'a'; 
            // while (j >= 0 && pat[j] != cs[i]) j = nfa[j]; in kmp
            while (j != root && j.chds[idx] == null) j = j.next;
            if (j.chds[idx] == null) continue;
            j = j.chds[idx]; // j++;
            if (j.isWord) {
                wordCnt++;
                j.isWord = false;
            }
        }
        return wordCnt;
    }

    public static void main(String[] args) {
        String text = "yasherhs";
        String[] words = {"she", "her", "say", "shr","rh"};
        ACTemplate acTemplate = new ACTemplate();
        for (String w : words) acTemplate.insert(w);
        acTemplate.buildNextPointer();
        System.out.println(acTemplate.query(text));
        // should be 3
    }
}

鉴于目前LC 还没有出过需要用到AC自动机的题目，所以就只简单给一个模板。模板中我们维护了节点是否为单词的信息。最后用来统计所有单词个数。不同题目要统计的信息不同，可能会改变NODE节点里存的信息不同。等之后有题目进来，我再过来更新。

总结

其实这篇文章主要是要讲KMP，然后怎么从KMP映射到AC自动机的扩展。

在 KMP中。我们从NEXT 数组的思想映射到DFA的KMP解法。

再扩展到NFA的KMP解法。本质是2点。

不变量的维护，每一次I进来，都必须有str.substring(0, j) == str(i - j, i)。
nfa里存的值要尽可能大。
有了第一个性质。我们就可以写出nfa[i] = pat[i] == pat[j] ? nfa[j] : j;
这个代码。
我们假设第二个性质存在，（自底向上可以数学归纳，证明0是对的。之后假设K对，K+1必对）所以我们可以假设nfa[k] 能返回尽可能大的值，然后我们贪心的找到J最大的位置。来维护下次循环时的第一个特性
就有了如下代码while (j >= 0 && pat[i] != pat[j]) j = nfa[j];

LEETCODE 有很多题目是基于前缀后缀最大公共长度值的，所以我们只要把第一个性质退化成nfa[i] = j;，然后最后补一个无用字母。就可以得到这个原始NEXT数组。

AC自动机就是建TRIE树, BFS根据KMP的模板改出BUILD_NEXT_POINTER的代码即可。

小伙伴可以拿LeetCode 28. Implement strStr() 来练习KMP模板。DFA解法

    public int strStr(String haystack, String pattern) {
        char[] pat = pattern.toCharArray(), cs = haystack.toCharArray();
        if (pat.length == 0) return 0;
        int[][] dfa = new int[pat.length][256];
        dfa[0][pat[0]] = 1;
        for (int i = 1, pre = 0; i < pat.length; i++) {
            dfa[i] = dfa[pre].clone();
            dfa[i][pat[i]] = i + 1;
            pre = dfa[pre][pat[i]];
        }
        int j = 0, i = 0;
        for (; i < cs.length && j < pat.length; i++) {
            j = dfa[j][cs[i]];
        }
        if (j == pat.length) return i - j;
        return -1;
    }

字符串算法(1)-KMP, AC自动机

1. 直觉

2. next array

为什么可以这么构造？

那么如何使用NEXT ARRAY呢？

3. 有限确定状态机

4. NFA解法

自底向上看

自顶向下看

AC自动机

AC自动机模板

总结

猜你喜欢

热点阅读