Skip to content

Tag Archives: 字符串匹配自动机

字符串匹配自动机

首先(不严谨地)定义自动机:自动机就是一堆状态的组合,给某个状态的自动机一个输入,它会按照自己的转移规则变到一个新的状态。事实上,可以把状态理解成顶点,把状态的转移理解成上面标着符号的边,在某个状态得到了某个符号的输入时,就转移到那条边指向的状态去。 先介绍单串匹配的自动机。对于M个字符的串S[1..M],一个用这个串进行模式匹配的自动机需要M+1个状态。设状态i输入ch时的转移为auto[i][ch]。状态转移时要满足:若当前在状态i,说明已输入的最后i个字符是S[1..i],若有多个状态满足这个定义,则应该在编号最大的状态。如何保证上述条件始终被满足呢?首先,auto[i][S[i+1]]=i+1,这是明显的。如果ch!=S[i+1],则auto[i][ch]肯定应该转移到某个小于等于i的状态,这个状态j应该满足:它是串S[1..j]是S[1..i]+ch的后缀,且j是最大的。找出j的方法是:计算每个i的“后缀状态”,也就是给自动机输入S[2..i]后自动机应该在的状态suffix[i],则当输入ch时应该转移的状态就是auto[suffix[i]][ch]的转移。计算suffix的方法是:suffix[i+1]=auto[suffix[i]][S[i+1]],suffix[1]=0。单字符串的自动机就是这样构造的。每次转移到状态M时,就找到了一个匹配。 值得注意的是,上述suffix数组所含的信息和KMP算法求出的所谓next数组其实是完全一致的。其实CLRS上也说,KMP算法就是通过少量的预处理实时地均摊O(1)地求出自动机的状态转移(大意)。也就是说,串匹配自动机也可以这样实现:首先通过预处理求出suffix数组,然后在状态i输入了字符ch时,需要转移到状态auto[i][ch],但是具体转移到哪个状态我们并没有预处理求出,我们只知道:若S[i+1]==ch则转移到i+1,否则转移到auto[suffix[i]][ch]。利用这两个条件,前者可以看做递归边界,就可以递归的求出每个需要的转移。可以证明的是这种求的复杂度是均摊O(1)的。 然后来看多字符串匹配的情况,其实和单字符串的时候差别不大,只不过状态之间不再是一个简单的线性结构了,而是一个Trie的结构,要根据刚才那个“后缀状态”的定义求出所有没有在Trie中直接出现的边应该转移到什么地方,同样也可以像KMP算法实时地计算那些转移。具体的方法都跟单串的没什么差别。 SPOJ上有两道题可以练习自动机:PSTRING是利用单串匹配自动机(或者KMP)进行状态转移的DP,WPUZZLES则是直接的多串自动机应用。 关于字符串匹配自动机,更详细的说明和更多应用可以找Maigo(王赟)关于Trie图的论文。