아주 간단한 구현으로 다음과 같은 문제를 해결해야 한다.

• 어떤 방식으로 효율적인 lookupwords을 생성할 것인가.
  
• 검색서비스에서의 경우 해당 질의어를 포함한 문서가 많은 단어 - DF -순으로 정렬 한다. 이러한 구현도 필요하다.
  
• 효율적인 자료구조에 대해서 생각해보자.
  
  1. 그럴려면 역시 효율적인 lookupwords 테이블의 구성이 필요할 것 같다.
     
  2. 복잡한 Tree 자료구조를 사용해야 하나 ?
     

#include <stdio.h> 
#include <string.h> 
 
#define MAXNODES  27 
#define MAXLAYERS 100 
#define COL(a)  ( a - 'a' + 1 ) 
#define IsLayer(a) ( ( a > 0 ) && (a < MAXLAYERS ) ) 
 
#define NUMOFWORDS 37 
#define NUMOFLOOKUPWORDS 15 
 
char * lookupwords[NUMOFLOOKUPWORDS] = { 
    "an", 
    "a", 
    "c", 
    "ca", 
    "co", 
    "o", 
    "or", 
    "s", 
    "t", 
    "to", 
    "y", 
    "yo", 
    "you", 
    "i", 
    "in" 
}; 
 
char * words[NUMOFWORDS] = { 
    "and", 
    "and", 
    "codepad", 
    "org", 
    "is", 
    "o", /*"an",*/ 
    "online", 
    "compiler", 
    "interpreter", 
    "a", 
    "simple", 
    "collaboration", 
    "tool", 
    "paste", 
    "your", 
    "code", 
    "below", 
    "codepad", 
    "will", 
    "run", 
    "it", 
    "and", 
    "give", 
    "you", 
    "a", 
    "short", 
    "url", 
    "you", 
    "can", 
    "use", 
    "to", 
    "share", 
    "it", 
    "in", 
    "chat", 
    "or", 
    "email" 
}; 
 
typedef struct _column { 
    union { char * pstr; int nlayer; } _field; 
} column, * pcolumn, ** ppcolumn; 
 
column g_Tbl[MAXLAYERS][MAXNODES]; 
int g_UnusedLayer=0; 
 
void PrintLayers() { 
    int i=1,j=0; 
    for(i=1;i<g_UnusedLayer;i++) { 
        for(j=0;j<MAXNODES;j++) { 
            printf ("i: %3d, j: %c >> ", i, j?'a'+j-1:'_');  
            if ( ! IsLayer(g_Tbl[i][j]._field.nlayer) && g_Tbl[i][j]._field.nlayer) 
                printf("%s\n", g_Tbl[i][j]._field.pstr); 
            else if ( IsLayer(g_Tbl[i][j]._field.nlayer) ) 
                printf("[%d]\n", g_Tbl[i][j]._field.nlayer); 
            else  
                printf("\n"); 
        } 
        getchar(); 
    } 
} 
 
void PrintLayer(int nlayer) { 
    int j; 
    if(nlayer==0) return; 
    else { 
        for(j=0;j<MAXNODES;j++) { 
            if ( ! IsLayer(g_Tbl[nlayer][j]._field.nlayer) && g_Tbl[nlayer][j]._field.nlayer) 
                printf("Candidate >> %s\n", g_Tbl[nlayer][j]._field.pstr); 
            else 
                PrintLayer(g_Tbl[nlayer][j]._field.nlayer); 
        } 
    } 
    return; 
} 
 
void FindCandidates(char *word) { 
    int i=1,j=0,nlenword,col; 
    nlenword=strlen(word); 
    while (word[j]) { 
        col=COL(word[j]); 
        if ( g_Tbl[i][col]._field.nlayer == 0 ) { 
            printf("No Candidates.\n"); 
            return; 
        } 
        else if ( !IsLayer(g_Tbl[i][col]._field.nlayer)  
            && g_Tbl[i][col]._field.nlayer) { 
            printf("Candidate >> %s\n", g_Tbl[i][col]._field.pstr); 
            return; 
        } 
        else if (IsLayer(g_Tbl[i][col]._field.nlayer)) 
            i = g_Tbl[i][col]._field.nlayer; 
        j++; 
    } 
 
    PrintLayer(i); 
 
    return; 
} 
 
void Add(char * word) { 
    int i=1,j=0,nlenword; 
    char * prevword; 
    int col; 
    nlenword=strlen(word); 
    while (word[j]) { 
        col=COL(word[j]); 
        if (g_Tbl[i][col]._field.nlayer == 0) { 
            g_Tbl[i][col]._field.pstr = word; 
            if( i > g_UnusedLayer ) { 
                if(g_UnusedLayer < MAXLAYERS) 
                    g_UnusedLayer = i+1; 
            } 
            return; 
        } 
        else if( IsLayer(g_Tbl[i][col]._field.nlayer) ) { 
            i = g_Tbl[i][col]._field.nlayer; 
        } 
        else if( ! strcmp (g_Tbl[i][col]._field.pstr, word) ) { 
            return; 
        } 
        else if( j < nlenword ) { 
            prevword = g_Tbl[i][col]._field.pstr; 
            g_Tbl[i][col]._field.nlayer = g_UnusedLayer; 
            i = g_UnusedLayer; 
            if(g_UnusedLayer < MAXLAYERS) 
                g_UnusedLayer++; 
            Add(prevword); 
        } 
        j++; 
    } 
    g_Tbl[i][0]._field.pstr = word; 
    return; 
}; 
 
#define __PRINT__ 
#undef  __PRINT__ 
#define __INTERACTIVE__ 
#undef  __INTERACTIVE__ 
 
int main(int argc, char * argv[]) { 
    int i; 
    char buf[128]=""; 
    memset(g_Tbl,0,sizeof(column)*MAXNODES*MAXLAYERS); 
 
    for(i=0;i<NUMOFWORDS;i++) { 
        Add(words[i]); 
 
#ifdef __PRINT__ 
        system("cls"); 
        printf("- %s : g_UnusedLayer : %d - \n", words[i], g_UnusedLayer); 
        PrintLayers(); 
#endif __PRINT__ 
 
    } 
 
#ifdef __INTERACTIVE__ 
    do { 
        printf("Lookup : "); 
        fgets(buf, 127, stdin); 
        buf[strlen(buf)-1]='\0'; 
        FindCandidates(buf); 
    } while (strcmp(buf,"quit")); 
#else  
    for(i=0;i<NUMOFLOOKUPWORDS;i++) { 
        printf("-- %s --\n", lookupwords[i]); 
        FindCandidates(lookupwords[i]); 
    } 
#endif __INTERACTIVE__ 
 
    return 0; 
}