点。?一个非根结点是危险结点的充要条件是:?它的路径字符串本身就是一个不良单词,或?它的路径字符串的后缀对应的结点是危险结点。?于是问题2转化为:如何求一个结点的后缀结点?7Trie图的构建(计算后缀结点)?根结点的后缀结点是它本身。?处于trie树第二层的结点的后缀结点也是根结点。?对于再往下的某个结点,设它的路径字符串的最后一个字符为c,那么这个结点的后缀为从它在trie树中父结点的后缀结点出发,沿标有c的边走一步后到达的结点。(下文中称从x结点出发,沿标有字符c的边走一步到达的结点为x的c孩子)?现在,问题2进一步转化为:如果它的父结点的后缀结点w没有c孩子怎么办呢?我们看到,两个问题已经合而为一了!8Trie图的构建(两个问题的解决)?我们假设w有这样一个c孩子(记作x),并且从x出发又繁衍出无数的子子孙孙。我们来判断x的危险性。显然x本身的路径字符串不是不良单词,且它的子孙的路径字符串也不是不良单词。因此以x为根的子树中任一结点y的危险性与y的后缀结点的危险性相同(回忆一下一个非根结点是危险结点的充要条件)。这也就是说,以x为根的子树与以x的后缀结点为根的子树是一模一样的。因此,我们把需要新建的从w指向x的边直接指向x的后缀结点,即w的后缀结点的c孩子即可。?简言之,由于w本身的路径字符串既不是不良单词,又不是某个不良单词开头的一部分,所以它的首字母便没有用了!在这种情况下,w结点就等价于它的后缀结点。9Trie图的构建(构建流程)?按层次遍历trie树,同时:?求出每个结点的危险性?求出每个结点的后缀结点?补齐由它出发的边?补边的方法为:?从根结点出发的补边指向根本身;?对非根结点x,若它没有c孩子,则新建一条边,从x指向x的后缀结点的c孩子。?处理某个结点的过程中需要用到深度比它小的结点的后缀结点及各个孩子。由于我们按层次遍历trie树,这些信息都已求得。10
全文预览
