What is the complexity of creating a lexicographic tree

W开发者_JAVA技巧hat is the complexity of creating a lexicographic tree?

If you create a prefix tree out of your input, you can perform this query in constant time.

Edit

The query is linear in the length of the search string. I meant that it was constant with regard to the size of the word list.

The appropriate data structure for this is probably a sorted list. In that case this becomes a bisection search problem, so O(log n).

As Gabe mentioned above Trie is good solution but it's little bit hard to implement for dictionaries with large number of words. If O(n log n) algorithm is OK for you, you can solve this problem with binary search. Here is code written in C:

char dict[n][m]; // where n is number of words in dictionary and 
                 // m is maximum possible length of word
char word[m];    // it's your word

int l = -1, r = n;
while(l+1 < r) {
  int k = (l+r)/2;
  if(strcmp(dict[k], word) < 0) l = k;
  else r = k;
}

int len = strlen(word);
l++; // first word's index with greater or equal prefix then word is l+1
bool matches = (strlen(word[l]) >= len);
for(int i = 0; i < len && matches; i++) {
  if(word[i] != dict[l][i]) {
    matches = 0;
  }
}

if(matches) {
  printf("given word is prefix of %dth word.", l);
} else {
  printf("given word isn't in dictinary.");
}

just run with a simple loop and check whether each word start with whatever.

in almost every language there is a build in function for check whether one string start with another.

the complexity is O(log n), while n being the number of the words in the dictionary.