// INPUT : char *str[] = { "one$", "two$", "three$", "four$",
// "thre$" };
// char *test[] = { "one$", "too$", "three$", "fore$" };
// OUTPUT : one$ is present, too$ is not present, three$ is
// present, fore$ is not present
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ASIZE 255
typedef struct node {
struct node *a[ASIZE];
} Node;
Node *newNode()
{
Node *n = (Node *) malloc(sizeof(Node));
int i;
for (i = 0; i < ASIZE; i++) {
n->a[i] = NULL;
}
return n;
}
void insertTrie(Node ** rootRef, char *str)
{
int len = strlen(str);
int i;
Node *root = *rootRef;
if (root == NULL) {
root = newNode();
*rootRef = root;
}
for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
root->a[p] = newNode();
}
root = root->a[p];
}
}
int isPresent(Node * root, char *str)
{
int len = strlen(str);
int i;
int isPresent = 1;
for (i = 0; i < len; i++) {
int p = str[i];
if (root->a[p] == NULL) {
isPresent = 0;
break;
} else {
root = root->a[p];
}
}
return isPresent;
}
printAllWordsRecur(Node *root,char *out,int len){
int i;
int done = 1;
for(i=0;i<ASIZE;i++){
if(root->a[i] == NULL){
continue;
} else{
done = 0;
out[len++] = i;
printAllWordsRecur(root->a[i],out,len);
len--;
}
}
if(done){
out[len] = '\0';
printf("%s\n",out);
}
}
printAllWords(Node *root){
static char out[50];
printAllWordsRecur(root,out,0);
}
int main()
{
char *str[] = { "one$", "two$", "three$", "four$", "thre$" };
char *test[] = { "one$", "too$", "three$", "fore$" };
Node *root = NULL;
int i;
for (i = 0; i < 5; i++) {
insertTrie(&root, str[i]);
}
for (i = 0; i < 4; i++) {
if (isPresent(root, test[i])) {
printf("%s is present\n", test[i]);
} else {
printf("%s is not present\n", test[i]);
}
}
printAllWords(root);
return 0;
}
No comments:
Post a Comment