字符串模式匹配中DFA的应用.pdf

字符串模式匹配中DFA的应用 北京大学信息学院郭炜 GWPL@PKU.EDU.CN 本讲义部分内容引用北大信息科学技术学院贺一骏讲义 POJ1204 Word Puzzles 题目大意: 给出一个N*L的字符矩阵，再给出M个字符串， 问这M个字符串在这个字符矩阵中出现的位置。 MARGARITA ALEMA BARBECUE 数据范围： N,L=1000 M=1000 时间限制：5s 将问题抽象 将N*L的字符矩阵中的每行、每列、每斜 行，单独抽出得到了N+L+2*(N+L-1)个字符串， 加上它们的各自的逆序，则得到的字符串的数 目是： 2*(N+L+2*(N+L-1))=6N+6L-2 然后，现在的问题是判断之后给出的M个 字符串出现在以上的那些字符串的什么位置。 这里我们称前面抽象出来的6N+6L-2个串为原 串，之后给出的M个串为模式串。 思考… 强行匹配？时间复杂度：O(NLMlen) (len是模式串的平均长度） O(1012) 太不靠谱了！！ KMP？时间复杂度：O(NLM) 9 O(10 ) 还是不能忍！！ 确定性有限状态自动机 DFA(deterministic finite automata) DFA使用一个五元组(Q，q0，A ，∑，δ)来描述，这里Q为状 态集；q0为起始状态；A为终态集； ∑为字母表，δ为转移函数。 用一个图来描述一个自动机： 这是一个字符集为01的 DFA S=“001110” 可以匹配它 图中圆圈代表状态，箭头代表转移，例如从状态 “1”有一 条字符0的边指向状态 “10”，就是说在状态“1”如果碰到输 入是’0’那么就转移到状态“10”。状态empty之前有一个start 标记，我们称empty状态为初态；状态“10”多加了一个圆圈， 我们称他为终态。自动机的初态只有一个而终态可以由若干个。 确定性有限状态自动机 DFA是一个图结构的数据结构，每一个节点都有字符集 字符数条有向边，并且之所以称之为确定性的，是由于 任何一个节点，都不会存在标有相同字符的有向边指向 不同的节点。为了更好的理解，我们再给出一个复杂一 点的例子，终态为’nano’的自动机如下图所示，能够判 断输入串里是否包含“nano” 为了解决多串匹配问题，我们下面将介绍一种DFA，他是树 结构的模型（一般图模型的DFA在应用中并不是很多）。 单词前缀树(trie) 这个树有一个性质，那就是m个模式串中的前缀所组成的集 合A与根节点到每一个树中的节点的路径上的字符组成的字 符串S所组成的集合B，是一个满射的关系,即树中任一节点， 都对应于某个模式串的前缀。 单词前缀树(trie) 将串s插入到trie 的代码描述如下： struct trienode { void build(string s) trienode * child[26] ; { //假设所有字符就是26个字母 trienode* p=root; tr