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的一个终态节点。雄钨淘颅钱斤众镑蹿耀冀亮乔步煤村古逞酶槛香捡假戈铺