算法合集之《Trie图的构建活用与改进》

Trie图的构建、活用与改进山东省龙口一中王赟Trie树与Trie图Trie树（左）是字典的一种存储方式。红色表示单词终止的位置。Trie图（右）是由Trie树改造成的图。为方便起见，仅画出了安全图。Trie图在多模式匹配中能发挥奇效。五个模式串：a,abc,bac,bbc,ca主串：cbcbbcac匹配成功！Trie图的构建（例1）【例1】不良单词探测器【题目描述】给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。【输入】第一行为一个整数n，表示不良单词的个数。接下来n行是词典。下面一行为一个整数m，表示文本的行数。接下来m行是文本。【输出】如果文本包含不良单词，输出一行“Yes”，否则输出一行“No”。Trie图的构建（例1）【样例输入】1rob1internetproblemsolvingcontest【样例输出】Yes【备注】因本题只是用来讨论trie图的构建方法，故未给出数据范围。Trie图的构建（例1分析）判断文本是否包含不良单词可以一行一行地判断。而判断长为L的一行文本s是否含有不良单词可以这样进行：让i从1变化到L，依次判断s的前i个字符构成的字符串是否以不良单词结尾。然而，我们希望在判断s的前k个字符时，能够利用前k-1个字符的结果，即这两个状态间可以方便地进行转移。注意到trie树中的边正如一个个“方向标”，因此我们有了一个美好的设想：从根结点出发，沿着标有s[1]的边走一步，再沿标有s[2]的边走一步，一直这样走下去！Trie图的构建（例1分析）问题1：如果从当前走到的结点出发，没有需要走的边，该怎么办？“创造”一条这样的边！但我们不能同时创造一个结点，因此我们需要在已有的结点中找一个与我们想要走到的结点“等价”的结点。什么叫“等价”？先看这样一个问题：定义trie树中从根结点到某个结点的路径上的边上的字符连起来形成的字符串为这个结点的路径字符串。如果一个结点的路径字符串以不良单词结尾，那么称这个结点为危险结点，否则称之为安全结点。问题2：如何判断某个结点是否危险？Trie图的构建（计算结点的危险性）再给出几个定义：一个字符串去掉第一个字符后剩下的部分叫做它的后缀。一个字符串对应的结点是指在trie图中从根出发，依次沿该字符串的每个字符走一步所达到的结点。一个结点的路径字符串的后缀对应的结点称为它的后缀结点。显然根结点是安全结点。一个非根结点是危险结点的充要条件是：它的路径字符串本身就是一个不良单词，或它的路径字符串的后缀对应的结点是危险结点。于是问题2转化为：如何求一个结点的后缀结点？Trie图的构建（计算后缀结点）根结点的后缀结点是它本身。处于trie树第二层的结点的后缀结点也是根结点。对于再往下的某个结点，设它的路径字符串的最后一个字符为c，那么这个结点的后缀为从它在trie树中父结点的后缀结点出发，沿标有c的边走一步后到达的结点。（下文中称从x结点出发，沿标有字符c的边走一步到达的结点为x的c孩子）现在，问题2进一步转化为：如果它的父结点的后缀结点w没有c孩子怎么办呢？我们看到，两个问题已经合而为一了！Trie图的构建（两个问题的解决）我们假设w有这样一个c孩子（记作x），并且从x出发又繁衍出无数的子子孙孙。我们来判断x的危险性。显然x本身的路径字符串不是不良单词，且它的子孙的路径字符串也不是不良单词。因此以x为根的子树中任一结点y的危险性与y的后缀结点的危险性相同（回忆一下一个非根结点是危险结点的充要条件）。这也就是说，以x为根的子树与以x的后缀结点为根的子树是一模一样的。因此，我们把需要新建的从w指向x的边直接指向x的后缀结点,即w的后缀结点的c孩子即可。简言之，由于w本身的路径字符串既不是不良单词，又不是某个不良单词开头的一部分，所以它的首字母便没有用了！在这种情况下，w结点就等价于它的后缀结点。Trie图的构建（构建流程）按层次遍历trie树，同时：求出每个结点的危险性求出每个结点的后缀结点补齐由它出发的边补边的方法为：从根结点出发的补边指向根本身；对非根结点x，若它没有c孩子，则新建一条边，从x指向x的后缀结点的c孩子。处理某个结点的过程中需要用到深度比它小的结点的后缀结点及各个孩子。由于我们按层次遍历trie树，这些信息都已求得。Trie图的构建（构建流程演示）结点后缀a孩子b孩子c孩子001491012924573391049405795112669104974578891049901049101129501942107863abcbcaccba图例：安全结点危险结点cbcabababacabcTrie图的构建（例1的解决）这样由trie树改造成的有向图就叫做trie图。图2就是由图1的trie树改造成的trie图。我们美好的设想终于变成了现实。由根结点出发，按照文本中的字符一步步走下去。若走到一个危险结点，则发现了一个不良单词；若一直没走到危险结点，则文本不含不良单词。Trie图的构建（例1的一点优化）本题的算法还可稍加优化。把安全结点分为两类：如果在trie树中由根结点到某个安全结点的路径上没有危险结点，那么称这个安全结点为真安全结点，否则称之为假安全结点。由于新建的边的终点的深度不会大于起点的深度，因此要到达一个假安全结点，必须经过一个危险结点。而在本题中，一旦到达一个危险结点，程序就会停止，因此假安全结点是没有用的，也就是说，在本题trie图的构建过程中，若发现一个危险结点，那么它及它的子孙的属性都不必计算了。Trie图的构建（复杂度分析）如果用L1、L2分别表示不良单词和文本的总长度，用a表示字符集中字符的个数，那么trie图的时间复杂度为O(L1a+L2)，空间复杂度为O(L1a)。Trie图的活用在上面的例题中，我们在trie图中记录了每个结点的危险性、后缀结点，并通过按层次遍历得到了图中结点的一个BFS序。其实，trie图中可以记录的信息不止这些；得到的BFS序也并不是毫无用处。Trie图的活用（例2）【例2】字谜（题目来源：SPOJWPUZZLES）【题目描述】给定一个L行C列的、由大写字母构成的矩阵，以及W个单词。每个单词可在矩阵中的任何位置朝着任何方向出现，且仅出现一次。编程找出每个单词的首字母在矩阵中的位置，以及单词的朝向。【输入（标准输入）】第一行为一个整数T，表示数据的组数。下面有T组数据。每组数据中：第1行为三个不超过1000的整数L、C、W。下面L行，每行C个大写字母，表示矩阵。下面W行，每行一个单词。Trie图的活用（例2）【输出（标准输出）】对每组数据，输出W行，每行为两个整数和一个字母，之间用一个空格隔开。第i行的两个整数表示第i个单词首字母的行号和列号（从上至下依次为第0至L-1行，从左往右依次为第0至C-1列）；字母表示单词的朝向，对应关系如下：相邻两组数据的输出之间用一个空行隔开。字母ABCDEFGH朝向上右上右右下下左下左左上Trie图的活用（例2）【样例输入】1454MAIGOQKRPTAREMOWERTYAKIMAIGOARMARMY【样例输出】20B00C01D01DTrie图的活用（例2分析）本题中多模式匹配的模型是显而易见的。由于要求的是每个单词首字母的位置，我们在建trie图时，把每个单词都反过来，如单词MAIGO变成OGIAM。对每个方向的每一串字母进行一次多模式匹配，就可以找到所有的单词了。在本题的trie图中，仅仅记录每个结点的危险性是不够的，还要记下每个结点的危险性是由哪个单词引起的。我们定义危险结点x的危险源：若x的路径字符串本身就是不良单词，那么它的危险源就是该单词；否则x的危险源就是它后缀结点的危险源。每个结点的危险源可以在后缀结点的过程中求出。Trie图的活用（例2分析）MAIGOQKRPTAREMOWERTY那么，是不是每走到一个危险结点，便记下危险源的位置及朝向就可以了呢？不是的。比如在样例中，当我们沿着左上方向扫描(3,4)-(0,1)这个字符串（YMRA），到达字母A时，由于该结点的危险源是YMRA，我们便记下了ARMY的位置和朝向。但同时我们就把单词ARM漏掉了。正确的做法是，当遇到一个危险结点时，记下它的危险源的位置和朝向，同时继续检查危险源对应结点的后缀结点，直到到达一个安全结点为止。Trie图的活用（例2的遗留问题）例2的字符集虽然只有26个字母，但trie图中结点的数目可能达到1,000,000，内存复杂度太高。这个问题留待第三部分（trie图的改进）解决。Trie图的活用（BFS序的应用）通过《字谜》一题我们学会了如何在trie图中记下更多的信息。下面简述一下对BFS序的应用。在做多模式匹配时，有时仅仅找到不良单词是不够的，还要统计出每个单词出现的次数。进行这项工作时，我们并不需要判断每个结点的危险性，而只需累加经过每个结点的次数。但这时有单词对应的结点的访问次数并不就是这个单词出现的次数，比如在图2中，单词a出现时光标完全可能在结点ba上。因此我们自底向上地把每个结点的访问次数加到它的后缀结点上。这样处理之后，有单词对应的结点的访问次数就代表这个单词出现的次数了。Trie图的活用上面介绍了trie图的一些初步活用。但如果仅仅用trie图来做多模式匹配，那就太大材小用了。下面再通过几个例题来说明trie图的更灵活的应用。从例1可以看到，危险结点在图中往往是一些障碍，在许多用到trie图的问题中，有用的结点只有真安全结点。我们把trie图中的真安全结点以及它们之间的边构成的子图叫做安全图。Trie图的活用（例3）【例3】病毒（题目来源：POI#7）【题目描述】已知某些特定的01串是病毒的特征代码。如果一个01串不含有任何病毒特征代码，则称它为一段安全代码。给定病毒特征库，判断是否存在无限长的安全代码。【输入（文件wir.in）】第一行为一个整数n，表示病毒特征代码的条数。下面n行，每行一段病毒特征代码。所有代码长度之和不超过30000。【输出（文件wir.out）】若存在无限长的安全代码，输出一行“TAK”，否则输出一行“NIE”。Trie图的活用（例3分析）【样例输入】3011100000【样例输出】NIE【分析】“无限长”的安全代码是什么意思呢？就是说从根结点出发，在安全图中可以走无限步。“无限步”又是什么意思呢？就是说安全图中有环。因此我们建立一个trie图并对其安全图进行拓扑排序，若成功，则安全图无环，输出“NIE”，否则输出“TAK”。Trie图的活用（例4）【例4】Censored!（题目来源：Ural1158）【题目描述】已知一个由n(1=n=50)个字符组成的字符集及p(0=p=10)个不良单词（长度均不超过10），求长度为m(1=m=50)且不含不良单词的字符串的数目。【输入（标准输入）】第一行为三个整数n,m,p。第二行为n个字符，表示字符集。下面p行，每行一个不良单词。【输出（标准输出）】一个整数，表示长度为m且不含不良单词的字符串的数目。【样例输入】333QWEQQWEEQ【样例输出】7Trie图的活用（例4分析）求长度为m且不含不良单词的字符串的数目，就是求在安全图中从根结点出发走m步有多少种走法。用count[step,x]表示从根结点出发走step步到结点x的走法数，则容易写出右面的伪代码：显然，本题还需要用高精度。fillchar(count,sizeof(count),0);count[0,根]:=1;forstep:=1tomdofor安全图中每条边(i,j)doinc(count[step,j],count[step-1,i]);ans:=0;for安全图中每个结点xdoinc(ans,count[m,x]);Trie图的活用（小结）我们看到，trie图的安全图上还是大有文章可做的