Поиск Trie в O (N) в C

Question

Как вы можете пройти через trie в O (n) раз в C. Я думал о том, что цикл цикла for, проходящий через уровень 1, ищет корневой связанный список, если письмо затем сопоставлен поиск в этом списке, но даст мне n^2 раза. Есть ли способ ускорить его?

Спасибо!

Answer 1

Что такое «n», которое используется в «O (n)»? Если n означает число символов в строке поиска, следующий код может быть выполнен в O (n) времени.

/* structure of Trie node */ 
struct trieNode { 
    char *value; 
    childNode children(); 
    int childCount; 
} 

/* structure for childnode in a Trie node. Whichi contains 'key' and pointer to child node */ 
struct childNode { 
    char key; 
    trieNode *node; 
} 


/* setup Trie and search string. (not real code) */ 
trieNode root=createTrinode(...) ; /* Setup Trie of your problem. */ 
char* searchString = inputSearchString(...); /* get string for search */ 

int i; 
trieNode curNode; 

curNode = root; 
for i=0 to len(searchString)-1 
{ 
    curNode = findChildren(curNode,searchString(i)); /* findChildren function returns childnode of first argument, whose key is equal to second argument. (Code of findChildren is omitted) */ 
} 

/* curNode is the traversed leaf node by searchStrin */ 

индекс для цикла составляет от 0 до п (длина SearchString) -1, так что этот код может выполнить Jn O (N) времени.

Этот код не учитывает случай, когда serach-string не содержится в данном Trie.