Created
December 27, 2015 07:32
-
-
Save aulisius/37ad1b797b88e3d9b8c9 to your computer and use it in GitHub Desktop.
Basic autocomplete using trie in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//Basic autocomplete using a Trie | |
//The trie is really not efficient | |
//The words should be supplied in a dict.txt file. | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
typedef struct n { | |
struct n *subtrie[26]; | |
int isEnd; | |
} trie; | |
void insert(trie *ele, char *word) { | |
trie *root = ele; | |
int len = strlen(word); | |
for (int i = 0; i < len; i++) { | |
trie *curr = ele->subtrie[word[i] % 97]; | |
if (curr == NULL) { | |
curr = malloc (sizeof (trie)); | |
curr->isEnd = 0; | |
for(int i = 0; i < 26; i++) curr->subtrie[i] = NULL; | |
} | |
if(i + 1 == len) curr->isEnd = 1; | |
ele->subtrie[word[i] % 97] = curr; | |
ele = ele->subtrie[word[i] % 97]; | |
} | |
ele = root; | |
} | |
char *append (char *slice, char part) { | |
char *str = malloc (sizeof (char) * (strlen (slice) + 2)); | |
int i = 0; | |
while (slice[i] != '\0') str[i] = slice[i++]; | |
str[i++] = part; | |
str[i] = '\0'; | |
return str; | |
} | |
void print(trie *ele, char *slice) { | |
if (ele == NULL) return; | |
if (ele->isEnd) printf("%s\n", slice); | |
for (int i = 0; i < 26; i++) | |
if(ele->subtrie[i] != NULL) | |
print (ele->subtrie[i], append (slice, i + 97)); | |
} | |
void autocomplete(trie *ele, char *prefix) { | |
int len = strlen (prefix); | |
for (int i = 0; i < len; i++) ele = ele->subtrie[prefix[i] % 97]; | |
print (ele, prefix); | |
} | |
int main() { | |
trie n; | |
n.isEnd = 0; | |
for (int i = 0; i < 26; i++) n.subtrie[i] = NULL; | |
FILE *fp = fopen ("dict.txt", "r"); | |
char str[25]; | |
while (!feof (fp)) { | |
fscanf (fp, "%s", str); | |
insert (&n, str); | |
} | |
fclose (fp); | |
char input[100]; | |
while (1) { | |
printf (">> "); | |
scanf ("%s", input); | |
autocomplete (&n, input); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment