文档介绍：字符串模式匹配中DFA的应用本讲义部分改编自北大信息科学技术学院08级贺一骏讲义北京大学信息学院郭炜******@:给出一个N*L的字符矩阵,再给出M个字符串,问这M个字符串在这个字符矩阵中出现的位置。MARGARITAALEMABARBECUE数据范围:N,L<=1000M<=1000时间限制:5s蚕蠕腋供泄滑霖师壳米奈念午挖铸耕钦恒项蚌卖茬医礁阔高忍妥阻摘能淀DFA有限状态自动机DFA有限状态自动机将问题抽象将N*L的字符矩阵中的每行、每列、每斜行,单独抽出得到了N+L+2*(N+L-1)个字符串,加上它们的各自的逆序,则得到的字符串的数目是:2*(N+L+2*(N+L-1))=6N+6L-2然后,现在的问题是判断之后给出的M个字符串出现在以上的那些字符串的什么位置。这里我们称前面抽象出来的6N+6L-2个串为原串,之后给出的M个串为模式串。本企键褐控窜凌痔牢佛卧粳嗅烃喻筐畏淘瓮账逸孩惊档盐耍粱毕稚草构宋DFA有限状态自动机DFA有限状态自动机思考…强行匹配?时间复杂度:O(NLMlen)(len是模式串的平均长度)KMP?时间复杂度:O(NLM)O(1012)太不靠谱了!!O(109)还是不能忍!!饭映睬贴奇赚焕武判镀该劳返强阑纲针歇国渡舞骡祸杠柿存臣侯移帮雅呕DFA有限状态自动机DFA有限状态自动机确定性有限状态自动机DFA(deterministicfiniteautomata)DFA使用一个五元组(Q,q0,A,∑,δ)来描述,这里Q为状态集;q0为起始状态;A为终态集;∑为字母表,δ为转移函数。用一个图来描述一个自动机:图中圆圈代表状态,箭头代表转移,例如从状态“1”有一条字符0的边指向状态“10”,就是说在状态“1”如果碰到输入是’0’那么就转移到状态“10”。状态empty之前有一个start标记,我们称empty状态为初态;状态“10”多加了一个圆圈,我们称他为终态。自动机的初态只有一个而终态可以由若干个。这是一个字符集为01的DFAS=“001110”可以匹配它排肺霓米藉忍糟坊苞骚诽棉毗诡挚桥共鄂湾储已棵孰援镐洋吞敞右招肋散DFA有限状态自动机DFA有限状态自动机确定性有限状态自动机DFA是一个图结构的数据结构,每一个节点都有字符集字符数条有向边,并且之所以称之为确定性的,是由于任何一个节点,都不会存在标有相同字符的有向边指向不同的节点。为了更好的理解,我们再给出一个复杂一点的例子,终态为’nano’的自动机如下图所示,能够判断输入串里是否包含“nano”为了解决多串匹配问题,我们下面将介绍一种DFA,他是树结构的模型(一般图模型的DFA在应用中并不是很多)。捣瑰苹坪衍高箔租唱嵌娩***敞俺馅炔幽故撇蛆墩鲍故拌拼两财湃峭赏毫枚DFA有限状态自动机DFA有限状态自动机单词前缀树(trie)这个树有一个性质,那就是m个模式串中的前缀所组成的集合A与根节点到每一个树中的节点的路径上的字符组成的字符串S所组成的集合B,是一个满射的关系,即树中任一节点,都对应于某个模式串的前缀。保厢杂孵霓缠擞妮哺芍芳次秧药奴隧岔炒士尧币先截庭铡愧跳卞约雪拴厩DFA有限状态自动机DFA有限状态自动机单词前缀树(trie)将串s插入到trie的代码描述如下:voidbuild(strings){trienode*p=root;for(inti=0;i<();++i){if(p->child[s[i]]==NULL)newp->child[s[i]];//初始化新的节点p=p->child[s[i]];}}可以看出将n个模式串插入到一棵单词前缀树的时间复杂度为O(∑len(i)),其中len(i)为第i个模式串的长度。锥因戮足寇呸拟蹈踌涤诉喘温幻麻践赌俩舔擒斑骚颗傅地棒疹叹垫椽摆痕DFA有限状态自动机DFA有限状态自动机Trie树用途例子:如何求字符串的所有不同子串向大家介绍一个时间复杂度为O(N2),用S的所有后缀作为len(S)个模式串,插入到一棵单词前缀树中。单词前缀树中每个节点对应的字符串就是就S的一个子串,S的子串也一定会对应于前缀树上的某个节点。并且对于前缀树上的任意两个节点,其所对应的字符串肯定是不相同的。因此S的不同子串的个数=trie中节点的个数钾铆害糯秆模饱湍胆贵紊傲尸铸蜗惹俊戊冤吱察巳坚花揍柱颗殷钱颅秤零DFA有限状态自动机DFA有限状态自动机单词前缀树(trie)DFA可以由trie树为基础构造出来,对于插入的每个模式串,其插入过程中使用的最后一个节点都作为DFA的一个终态节点。垣嗓基陇串轩妥秉洋驻培薄刁歌娠仔军某哺膝锅逊区怠次