가장 긴 접두어 일치

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"은 조각으로 trie에 있지만, 단어가 "on"으로 설정되어 있지 않으므로 이라는 단어가 인 경우 end이 아닙니다. 이 코드는 다음 문자 "e"로 트리를 등반하지만 계속 변경되지 않습니다. prevMatch. 그러나 "e"를 볼 때 과이 일치하므로 end이라는 단어가 트리에 있으므로이 코드는 3을 prevMatch에 저장하기 때문에 end입니다.

Answer 2

단어가 끝나면 IsEnd killswitch가 설정되지만 trie 또는 검색의 끝이 아닙니다. 단어는 사전 적으로 트리 또는 해시 맵에 저장됩니다. 검색 단어가 첫 번째 또는 두 번째 킬 스위치가 아닐 수도 있습니다.