Trie最长的前缀匹配

Question

我没有得到trie这个词概念的结尾。我认为我对自己的理解并不完整。有人可以请解释在代码HERE

// If this is end of a word, then update prevMatch 
       if(crawl.isEnd()) 
        prevMatch = level + 1; 

Answer 1

当代码节节攀升线索寻找一个gifen字最长前缀，就会出现此以下的一段。

假设你有一个已经包含单词的线索：

“的” “一” “曾经”

和您要搜索的“繁重”的最长前缀，你会期望在3（即“一”出来的是最长前缀已经存在

正在执行的代码读取：

// See if there is a Trie edge for the current character 
    if (child.containsKey(ch)) { 
     result += ch;   //Update result 
     crawl = child.get(ch); //Update crawl to move down in Trie 

     // If this is end of a word, then update prevMatch 
     if (crawl.isEnd()) { 
      prevMatch = level + 1; 
     } 
    } else { 
     break; 
    } 

所以想象你正在看“n”的“繁重”。你会发现“on”是作为片段而不是end（因为你没有把单词“on”放在句子中，但是在那里单词“one”是）。此代码将继续爬下树，并显示下一个字符“e”，但不会更改prevMatch。然而，在查看“e”时，树和中存在匹配，因为单词“one”在树中，所以该代码存储3在prevMatch中，因此它是end。

Answer 2

当单词结束时，IsEnd killswitch被设置，但它不是句号或搜索的结尾。单词被存储在一个树或散列表中。它可能发生搜索词不是第一个或第二个杀戮开关。