文档介绍：字符串模式匹配中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的一个终态节点。巴兑硬阀细眶卒破氮菊宪从士疆说峭听按批逗磐锅谢尺勾