DFA有限状态自动机.pptVIP

bool 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; } int 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 Pandora 有n个各不相同的长度不超过1,000的模式串（0n=250），和一个长度不超过5,100,000的母串。如果母串包含某个模式串或其反转（“ABCD”的反转是“DCBA”），则称母串被模式串感染。问母串一共被多少个模式串感染。 2010 福州赛区题目 Computer Virus on Planet Pandora 1) 给模式串编上号，Trie图上每个终止节点记下它所对应的模式串的编号。为每个模式串设置一个是否已经被匹配的标记。走到某终止节点，就能知道哪个模式串被匹配，就设置其标记。 2)要注意的是，本题中，模式串里有可能一个串A是另一个模式串B的子串，在这种情况下，用母串在Trie图上跑一遍，就可能会发生走到B串的终止节点，即作出B被匹配的结论，但是却忽略了匹配B的过程中A其实也已经能够匹配这个情况。 2010 福州赛区题目 Computer Virus on Planet Pandora 2) 的解决办法： 对Trie图上的每个节点设置一个“是否计算过”的标记，初始值全部为假。假定在原Trie树上的节点x所对应的字符串为s，那么x节点“已计算过”，就意味着s的所有模式子串，都已经被标记为“已匹配”。在用母串在Trie图上跑的过程中，每到达一个“未计算过”的节点，就将该节点标记为“已计算过”，然后就要将该节点对应的s的所有后缀模式串(既是s的后缀，又是模式串的字符串)都标记为“已匹配”(s的非后缀模式子串在扫描到s之前就已经被标记为“已匹配”了。这个标记的过程，就是沿着节点的后缀指针一直走到根节点，将路径上(包括起点)的每个模式串的终止节点所对应的模式串，都标记为“已匹配”。显然，这条路上的每个节点在Trie树上对应的字符串，都是s的后缀，而且所有既是s的后缀，且在Trie树上有对应节点的字符串，其对应节点也一定会出现在这条路经上。 小结 KMP和DFA充分利用了当前已知的信息，构造出了NEXT数组和前缀指针，避免了比较过程中冗余，从而提高了算法的效率。 以上只是DFA很小的一个应用。 DFA不但可以高效的处理多串模式匹配问题，而且在字符串模式匹配问题上，提供了一个新的数据储存结构，从而可以达到一些意想不到的效果。在DFA上进行动归，是常见的做法。 我们接着看下一道题 POI #7 题：病毒 已知若干个01串，他们是病毒的特征代码。如果一段程序（由01组成）不含有任何病毒特征代码，则称它为安全程序。请判断是否存在无限长的安全程序。 “无限长”的安全母串，在Trie图上，从根节点出发，可以永远不停地走下去，即走无限步，都不会路过 “不安全节点”， 而Trie图节点是有限的……. 模式串对应的终止节点是“不安全”节点，如果有一个节点，它的前缀指针指向的节点是“不安全”节点，那么它也是“不安全节点”。 “无限长”的安全母串，在Trie图上，从根节点出发，可以永远不停地走下去，即走无限步，都不会路过 “不安全节点”， 而Trie图节点是有限的……. 只需判断，Trie图上，由安全节点构成的子图上，有没有环即可，有，就能无限走下去 Trie图上进行动归：POJ 3691 DNA repair 给定不超过50个由 ‘A’, ‘G’ , ‘C‘ ，’T’. 四个字母组成的模式串，每个模式串长度不超过20，再给一个不超