AC算法编程思维(算法和编程思维)

那些经典算法：AC自动机

第一次看到这个名字的时候觉得非常高级，深入学习就发现，AC就是一种多模式字符串匹配算法。前面介绍的BF算法，RK算法，BM算法，KMP算法都属于单模式匹配算法，而Trie树是多模式匹配算法，多模式匹配算法就是在一个主串中查找多个模式串，举个最常用的例子，比如我们在论坛发表评论或发帖的时候，一般论坛后台会检测我们发的内容是否有敏感词，如果有敏感词要么是用***替换，要么是不让你发送，我们评论是通常是一段话，这些敏感词可能成千上万，如果用每个敏感词都在评论的内容中查找，效率会非常低，AC自动机中，主串会与所有的模式串同时匹配，这时候就可以利用AC自动机这种多模式匹配算法来完成高效的匹配，AC自动机算法是构造一个Trie树，然后再添加额外的失配指针。这些额外的适配指针准许在查找字符串失败的时候进行回退（例如在Trie树种查找单词bef失败后，但是在Trie树种存中bea这个单词，失配指针会指向前缀be），转向某些前缀分支，免于重复匹配前缀，提高算法效率。常见于IDS软件或病毒检测软件中病毒特征字符串，可以构建AC自动机，在这种情况下，算法的时间复杂度为输入字符串的长度和匹配数量之和。假设现有模式字符串集合：{abd,abdk, abchijn, chnit, ijabdf, ijaij} 构建AC自动机如下：1）当前指针curr指向AC自动机的根节点：curr=root。2）从文本串中读取（下）一个字符。3）从当前节点的所有孩子节点中寻找与该字符匹配的节点：4）若fail == null，则说明没有任何子串为输入字符串的前缀，这时设置curr = root，执行步骤2.若fail != null,则将curr指向 fail节点，指向步骤3。理解起来比较复杂，找网上的一个例子，假设文本串text = “abchnijabdfk”。查找过程如下：1）按照字符串顺序依次遍历到：a-->b-->c-->h ,这时候发现文本串中下一个节点n和Trie树中下一个节点i不匹配，且h的fail指针非空，跳转到Trie树中ch位置。注意c-->h的时候判断h不为结束节点，且c的fail指针也不是结束节点。2）再接着遍历n-->i,发现i节点在Trie树中的下一个节点找不到j，且有fail指针，则继续遍历，遍历到d的时候要注意，d的下一个匹配节点f是结束字符，所以得到匹配字符串：ijabdf，且d的fail节点也是d，且也是结束字符，所以得到匹配字符串abd，不过不是失败的匹配，所以curr不跳转。先将目标字符串插入到Trie树种，然后通过广度有限遍历为每个节点的所有孩子节点找到正确的fail指针。具体步骤如下：1）将根节点的所有孩子节点的fail指针指向根节点，然后将根节点的所有孩子节点依次入队列。2）若队列不为空：2.1）出列一个字符，将出列的节点记为curr，failTo表示curr的fail指针，即failTo = curr.fail 。2.2) 判断curr.child[i] == failTo.child[i]是不是成立：成立：curr.child[i].fail = failTo.child[i]因为当前字符串的后缀和Tire树的前缀最长部分是到fail，且子字符和failTo的下一个字符相同，则fail指针就是failTo.child[i]。不成立：判断failTo是不是为null是否成立：成立： curr.child[i].fail = root = null。不成立： failTo = failTo.fail 继续2.2curr.child[i]入列，再次执行步骤2）。3）队列为空结束。每个结点的fail指向的解决顺序是按照广度有限遍历的顺序完成的，或者说层序遍历的顺序进行，我们根据父结点的fail指针来求当前节点的fail指针。上图为例，我们要解决y节点的fail指针问题，已经知道y节点的父节点x1的fail是指向x2的，根据fail指针的定义，我们知道红色椭圆中的字符串序列肯定相等，而且是最长的公共部分。依据y.fail的含义，如果x2的某个孩子节点和节点y表示的表示的字符相等，y的fail就指向它。如果x2的孩子节点中不存在节点y表示的字符。由于x2.fail指向x3，根据x2.fail的含义，我们知道绿色框中的字符序列是相同的。显然如果x3的某个孩子和节点y表示字符相等，则y.fail就指向它。如果x3的孩子节点不存在节点y表示的字符，我们重复这个步骤，直到xi的fail节点指向null，说明我们达到顶层，只要y.fail= root就可以了。构造过程就是知道当前节点的最长公共前缀的情况下，去确定孩子节点的最长公共前缀。下图中，每个节点都有fail虚线，指向根节点的虚线没画出，求图中c的孩子节点h的fail指向：原图中，深蓝色的框出来的是已经确定fail指针的，求红色框中h节点的fail指针。这时候，我们看下h的父亲节点c的fail指针指向，为ch中的c（这表示abc字符串的所有后缀bc和c和Trie树的所有前缀中最长公共部分为c），且这个c节点的孩子节点中有字符为h的字符，所以图中红色框中框出的h节点的fail指针指向 ch字符串中的h。求红色框中i的fail指针指向，上图中，我们可以看到i的父亲节点h的指向为ch中的h，（也就是说我们的目标字符串结合中所有前缀和字符序列abch的所有后缀在Trie树中最长前缀为ch。）我们比较i节点和ch中的h的所有子节点，发现h只有一个n的子节点，所以没办法匹配，那就继续找ch中h的fail指针，图中没画出，那么就是它的fail指针就是root，然后去看root所有子节点中有没有和i相等的，发现最右边的i是和我们要找的i相等的，所以我们就把i的fail指针指向i，如后面的图。