null字符串模式匹配中DFA的应用字符串模式匹配中DFA的应用本讲义部分改编自北大信息科学技术学院08级贺一骏讲义北京大学信息学院 郭炜
GWPL@PKU.EDU.CNPOJ1204 Word PuzzlesPOJ1204 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是模式串的平均长度）KMP？ 时间复杂度：O(NLM)O(1012) 太不靠谱了！！O(109) 还是不能忍！！确定性有限状态自动机DFA(deterministic finite automata) 确定性有限状态自动机DFA(deterministic finite automata) DFA使用一个五元组(Q，q0，A，∑，δ)来描述，这里Q为状态集；q0为起始状态；A为终态集； ∑为字母表，δ为转移函数。用一个图来描述一个自动机： 图中圆圈代表状态，箭头代表转移，例如从状态 “1” 有一条字符0的边指向状态 “10”，就是说在状态“1” 如果碰到输入是’0’那么就转移到状态“10” 。状态empty之前有一个start标记，我们称empty状态为初态；状态“10”多加了一个圆圈，我们称他为终态。自动机的初态只有一个而终态可以由若干个。这是一个字符集为01的DFA
S=“001110” 可以匹配它确定性有限状态自动机确定性有限状态自动机DFA是一个图结构的数据结构，每一个节点都有字符集字符数条有向边，并且之所以称之为确定性的，是由于任何一个节点，都不会存在标有相同字符的有向边指向不同的节点。为了更好的理解，我们再给出一个复杂一点的例子，终态为’nano’的自动机如下图所示，能够判断输入串里是否包含“nano”为了解决多串匹配问题，我们下面将介绍一种DFA，他是树结构的模型（一般图模型的DFA在应用中并不是很多）。 单词前缀树(trie) 单词前缀树(trie)这个树有一个性质，那就是m个模式串中的前缀所组成的集合A与根节点到每一个树中的节点的路径上的字符组成的字符串S所组成的集合B，是一个满射的关系,即树中任一节点，都对应于某个模式串的前缀。 单词前缀树(trie)单词前缀树(trie)将串s插入到trie的代码描述如下：
void build(string s)
{
trienode* p=root;
for (int i=0;i
child[s[i]]==NULL)
new p->child[s[i]]; //初始化新的节点
p=p->child[s[i]];
}
}
可以看出将n个模式串插入到一棵单词前缀树的时间复杂度为O(∑len(i)) ，其中len(i)为第i个模式串的长度。Trie树用途例子：如何求字符串的所有不同子串Trie树用途例子：如何求字符串的所有不同子串 向大家介绍一个时间复杂度为O(N2)的算法.
假设当前的字符串为S，用S的所有后缀作为len(S)个模式串，插入到一棵单词前缀树中。
单词前缀树中每个节点对应的字符串就是就S的一个子串，S的子串也一定会对应于前缀树上的某个节点。并且对于前缀树上的任意两个节点，其所对应的字符串肯定是不相同的。因此
S的不同子串的个数=trie中节点的个数单词前缀树(trie)单词前缀树(trie)
DFA可以由trie树为基础构造出来，
对于插入的每个模式串，其插入过程中使用的最后一个节点都作为DFA的一个终态节点。
前缀指针前缀指针仿照KMP算法的Next数组，我们也对树上的每一个节点建立一个前缀指针。这个前缀指针的定义和KMP算法中的next数组相类似，从根节点沿边到节点p我们可以得到一个字符串S，节点p的前缀指针定义为：指向树中出现过的S的最长的后缀，换句话说就是在前缀集中出现的最长的S的后缀。 如何高效的构造前缀指针如何高效的构造前缀指针 如果采用枚举法求前缀指针，那复杂度可想而知为O(n2)。我们利用当前节点的父节点所求出的前缀指针，来求当前节点的前缀指针，就可以将复杂度降为O(n)。 步骤为：根据深度一一求出每一个节点的前缀指针。对于当前节点，设他的父节点与他的边上的字符为Ch，如果他的父节点的前缀指针所指向的节点的儿子中，有通过Ch字符指向的儿子，那么当前节点的前缀指针指向该儿子节点，否则通过当前节点的父节点的前缀指针所指向点的前缀指针，继续向上查找，直到到达根节点为止。 如何高效的构造前缀指针如何高效的构造前缀指针ROOT1号节点的前缀指针指向0号节点接下来按照BFS顺序构造每个节点的前缀指针定义虚拟节点0号节点，0号节点的所有连出的字边都连向ROOT1号节点2号节点：
父亲是1号节点，连接字符为A，查找父亲的前缀指针0号节点，是否有通过A连接的儿子。
有！于是2号节点的前缀指针指向1号节点3号节点：
父亲是1号节点，连接字符为B，查找父亲的前缀指针0号节点，是否有通过B连接的儿子。
有！于是3号节点的前缀指针指向1号节点4号节点：
父亲是2号节点，连接字符为B，查找父亲的前缀指针1号节点，是否有通过B连接的儿子。
有！于是4号节点的前缀指针指向3号节点5号节点：
父亲是3号节点，连接字符为A，查找父亲的前缀指针1号节点，是否有通过A连接的儿子。
有！于是5号节点的前缀指针指向2号节点8号节点：
父亲是7号节点，连接字符为B，查找父亲的前缀指针5号节点，是否有通过B连接的儿子。
没有，继续查找5号节点的前缀指针2号节点是否有通过B连接的儿子。
有！于是8号节点的前缀指针指向4号节点7号节点：
父亲是4号节点，连接字符为A，查找父亲的前缀指针3号节点，是否有通过A连接的儿子。
有！于是7号节点的前缀指针指向5号节点6号节点：
父亲是3号节点，连接字符为B，查找父亲的前缀指针1号节点，是否有通过B连接的儿子。
有！于是6号节点的前缀指针指向3号节点至此，这棵树的前缀指针我们就设计完成了！！对于一个插入了n个模式串的单词前缀树构造其前缀指针的时间复杂度为：O(∑len(i))如何在建立好的DFA上遍历如何在建立好的DFA上遍历 以上的单词前缀树+前缀指针就是确定性有限状态自动机的树形结构图(即trie图）的基本构造方式了。
接下来要解决的问题是，已知一个串S，如何利用这个串在当前已经建立好的DFA上进行遍历，看其是否包含某个模式串，以及其时间复杂度。
遍历的方法如下：从ROOT出发，按照当前串的下一个字符ch来进行在树上的移动。若当前点P不存在通过ch连接的儿子，那么考虑P的前缀指针指向的节点Q，如果还无法找到通过ch连接的儿子节点，再考虑Q的前缀指针…直到找到通过ch连接的儿子，再继续遍历。如果遍历过程中经过了某个终止节点，则说明S包含该终止节点代表的模式串.
这样遍历一个串S的时间复杂度是O(len(S))回到原问题回到原问题 下面我们回到原来的那个多串模式匹配问题。
有了DFA这个好工具之后，这道题目就可以很简单的解决了。具体步骤如下：
1.按照M个模式串构造出一个单词前缀树
2.将这个单词前缀树加上前缀指针
3.将原来6N+6L-2个原串在这个建立的DFA上进行遍历，将遍历到的终态的位置记录下来，便可以得到每个模式串在原串中出现的位置了。回到原问题回到原问题现在来考虑一下，我们完成这个问题的算法的时间复杂度(M个模式串的总长度为LEN)：
1.O(LEN)
2.O(LEN)
3.O((6N+6L-2)*len(i))=O(NL)
因此总的时间复杂度为O(LEN+NL)
一个很不错的算法！！最纯粹的Trie图题目最纯粹的Trie图题目给N个模式串，每个不超过个字符，再给M个句子，句子长度< 100 判断每个句子里是否包含模式串
N < 10, M < 10 ,字符都是小写字母5 8
abcde
defg
cdke
ab
f
abcdkef
abkef
bcd
bca
add
ab
qab
fnull#include
#include
#include
using namespace std;
#define LETTERS 26
int nNodesCount = 0;
struct CNode
{
CNode * pChilds[LETTERS];
CNode * pPrev;
bool bStopNode; //是否是终止节点（危险节点）
void Init() {
memset(pChilds,0,sizeof(pChilds));
bStopNode = false;
pPrev = NULL;
}
};
CNode Tree[200]; //10个模式串，每个10个字符，每个字符一个节点，也只要100个节点nullvoid Insert( CNode * pRoot, char * s)
{
for( int i = 0; s[i]; i ++ ) {
if( pRoot->pChilds[s[i]-'a'] == NULL) {
pRoot->pChilds[s[i]-'a'] =
Tree + nNodesCount;
nNodesCount ++;
}
pRoot = pRoot->pChilds[s[i]-'a'];
}
pRoot->bStopNode = true;
}nullvoid BuildDfa( )
{
for( int i = 0;i < LETTERS ;i ++ )
Tree[0].pChilds[i] = Tree + 1;
Tree[0].pPrev = NULL;
Tree[1].pPrev = Tree;
deque q;
q.push_back(Tree+1);
while( ! q.empty() ){
CNode * pRoot = q.front();
q.pop_front();null for( int i = 0; i < LETTERS ; i ++ ) {
CNode * p = pRoot->pChilds[i];
if( p) {
CNode * pPrev = pRoot->pPrev;
while( pPrev ) {
if( pPrev->pChilds[i] ) {
p->pPrev =
pPrev->pChilds[i];
if( p->pPrev->bStopNode )
p->bStopNode = true;
//自己的pPrev指向的节点是危险节点，则自己也是危险节点
break;
}
else
pPrev = pPrev->pPrev;
}
q.push_back(p);
}
}
} //对应于while( ! q.empty() )
}nullbool SearchDfa(char * s)
{
CNode * p = Tree + 1;
for( int i = 0; s[i] ;i ++ ) {
while(true) {
if( p->pChilds[s[i]-'a']) {
p = p->pChilds[s[i]-'a'];
if( p->bStopNode )
return true;
break;
}
else
p = p->pPrev;
}
}
return false;
}nullint main()
{
nNodesCount = 2;
int M,N;
scanf("%d%d",&N,&M); //N个模式串，M个句子
for( int i = 0;i < N; i ++ ) {
char s[20];
scanf("%s",s);
Insert(Tree + 1,s);
}
BuildDfa();
for( int i = 0 ;i < M;i ++ ) {
char s[200];
scanf("%s",s);
cout << SearchDfa(s) << endl;
}
return 0;
}2010 福州赛区题目
Computer Virus on Planet Pandora2010 福州赛区题目
Computer Virus on Planet Pandora
有n个各不相同的长度不超过1,000的模式串（0
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
就是
Min{ Ans[len][j] | j 是DFA的安全节点 }
len是母串的长度试试DFA吧试试DFA吧状态转移方程为：
由Ans[i][j] 可以推出：
Ans[i+1][son[j]] = min { Ans[i+1][son[j]],
Ans[i][j] + ( Char(j,son[j]) != str[i] ) }
( Char(j,son[j]) != str[i] ) 表达式值为0或1
Char(j,son[j])表示从节点j走到节点son[j]所经过的字母
str是母串,下标从0开始算试试DFA吧试试DFA吧
Char(j,son[j] )表示从 j 到 son[j] 经过的字母,假设是a。
这里所说的“经过”，不仅指从j通过一条字母a边直接到达son[j], 也可以是通过若干前缀指针后再通过一个字母a边到达son[j]POJ1625 Censored!POJ1625 Censored!题目大意：
给出一个字符集V和P个模式串(长度小于10)，问由这个字符集中字符组成的长度为N的且不包含任意一个模式串的字符串有多少个？(字符集大小,N<=50, P <= 10)
样例：
输入：
2 3 1 //N=3 P=1
ab //字符集为ab
bb
输出：
5样例解释：
aaa
aab
aba
baa
bab
以上5个解题思路解题思路 这种类型的题目，如果使用搜索算法必然会导致超时的出现。因此，动态规划似乎是一种可行的
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
，我们来尝试构造一个状态。
Ans[i][j]表示长度为i且能走到节点j的字符串个数（节点j是安全节点）
初始Ans[0][1] = 1, 其他Ans[i][j] = 0
由Ans[i][j] 可以导出，每个由j可以到达的安全节点son[j],都应执行：
Ans[i+1][son[j]] += Ans[i][j]
因为从根走i步到达达节点j有 n种走法个，那么走i+1步到达son[j]的走法就要加n (因为j以外节点也可能通过一步走到j)
null这里所说的“到达”，不仅指从j(或从其他节点）通过一条字母边直接到达son[j], 也可以是通过若干前缀指针后再通过一个字母边到达son[j]
整个问题最终的答案就是：
∑ { Ans[N][j] | j 是安全节点 }
此题需要高精度计算
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
总结 像例题的题目还有很多，类似例题2的题目还有：
POJ2778 DNA Sequence
浙公网安备 33021202002483