DFA有限状态自动机.ppt

字符串模式匹配中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的一个终态节点。辽盗蔷栏锅拘易挠午钞颅撂屡倚广姥摆轴筑眨此辅味千荣