확장된 애너그램 사전만들기

#include <stdio.h>

#include <string.h>

// 확장된 anagram 알고리즘은 각 단어의 철자들을 가지고 만든 

// keyword (알파벳을 정렬한 다음 합쳐서 만든 문자열)

// 로 도달할 수 있는 노드를 가지고 부분의 철자로 만들 수 있는

// 단어들을 구하여 사전을 만들게 된다.

// 각 treeNode에서는 다음 알파벳에 따라서 해당하는 treeNode를 찾아 가게 된다.

// 이 <알파벳,트리노드> 는 각 알파벳에 해당하는 child[26] 으로 나타낸다.

// 각 노드까지 도달한 문자열을 나타내기 위해서  strs[6] (최대 갯수 6) 을

// 사용한다.

typedef struct _tree *pTree;

// 나무의 노드를 나타낸다.

// 이 노드로 부터 알파벳에 의해서 갈수 있는 다음 노드를

// 나타내는 child[26]과 현재 노드에 까지 온 문자열 strs[6] 을 가지고 있다.

typedef struct _tree {

    pTree   child[26];

    char    *strs[6];

} treeNode;

// keyword, word 쌍을 나타내는 구조체

typedef struct _pair *pPair;

typedef struct _pair {

    char *keyword;

    char *word;

    pPair next;

} pair;

// function prototypes 

pPair SortedMerge(pPair a, pPair b);

void FrontBackSplit(pPair source, pPair *frontRef, pPair *backRef);

// sorts the linked list by changing next pointers (not data) 

void MergeSort(pPair *headRef) {

    pPair head = *headRef;

    pPair a;

    pPair b;

 

    /* Base case -- length 0 or 1 */

    if ((head == NULL) || (head->next == NULL)) {

        return;

    }

 

    /* Split head into 'a' and 'b' sublists */

    FrontBackSplit(head, &a, &b); 

 

    /* Recursively sort the sublists */

    MergeSort(&a);

    MergeSort(&b);

 

    /* answer = merge the two sorted lists together */

    *headRef = SortedMerge(a, b);

}

//   See http://geeksforgeeks.org/?p=3622 for details of this 

//   function 

pPair SortedMerge(pPair  a, pPair b) {

    pPair result = NULL;

    pPair p;

 

    // Base cases 

    if (a == NULL) {

        return(b);

    } else if (b==NULL) {

        return(a);

    }

     

    if(strcmp(a->keyword, b->keyword)<=0) {

        result=a;

        a=a->next;

    } else {

        result=b;

        b=b->next;

    }

    p=result;

    while(a!=NULL && b!=NULL) {

    // Pick either a or b, 

        if (strcmp(a->keyword, b->keyword)<=0) {

            p->next = a;

            a=a->next;

            p=p->next;

        } else {

            p->next = b;

            b=b->next;

            p=p->next;

        }

    }

    if(a==NULL) {

        p->next=b;

    } else {

        p->next=a;

    }

   

    return(result);

}

 

// UTILITY FUNCTIONS */

// Split the nodes of the given list into front and back halves,

//   and return the two lists using the reference parameters.

//   If the length is odd, the extra node should go in the front list.

//   Uses the fast/slow pointer strategy.  

void FrontBackSplit(pPair source,

          pPair *frontRef, pPair *backRef) {

    pPair fast;

    pPair slow;

    if (source==NULL || source->next==NULL) {

        // length < 2 cases 

        *frontRef = source;

        *backRef = NULL;

    } else {

        slow = source;

        fast = source->next;

 

        // Advance 'fast' two nodes, and advance 'slow' one node 

        while (fast != NULL) {

            fast = fast->next;

            if (fast != NULL) {

                slow = slow->next;

                fast = fast->next;

            }

        }

 

        // 'slow' is before the midpoint in the list, so split it in two

        //  at that point. 

        *frontRef = source;

        *backRef = slow->next;

        slow->next = NULL;

    }

}

// Function to print nodes in a given linked list 

void printList(pPair node) {

    int i=0;

    while(node!=NULL) {

        printf("%s ", node->keyword);

        i+=1;

        node = node->next;

    }

}

void insertString(char *str, pTree tree) {

    int i;

    for(i=0;i<6;i+=1) {

        if(tree->strs[i]==NULL) { break; }

    }

    if(i<6) { 

        //printf("tree=%p str=%s [i=%d]\n", tree, str, i); if(i>3) getchar();

        tree->strs[i]=str;

    } else {

        printf("Fatal Error01\n"); getchar(); getchar();

    }

}

void insertNodes(char *key, char *word, pTree tree) {

    int i=0;

    char f=key[0], *s=key+1;

    char x;

    if(f==0) { 

        insertString(word, tree); 

        return;

    } 

    if(tree->child[f-'a']==NULL) {

        tree->child[f-'a']=(pTree)calloc(sizeof(treeNode), 1);

    }

    insertNodes(s, word, tree->child[f-'a']);

}

// Function to insert words in treeNode 

void insertWords(pPair node, pTree tree) {

    while(node!=NULL) {

        //printf("key=%s word=%s\n", node->keyword, node->word);

        insertNodes(node->keyword, node->word, tree);

        node = node->next;

    }

}

 

// Function to insert a node at the beginging of the linked list 

void push(pPair *head_ref, char *k, char *w) {

    // allocate node 

    pPair new_node = (pPair) malloc(sizeof(pair));

  

    // put in the data 

    new_node->keyword  = k;

    new_node->word = w;

  

    // link the old list off the new node 

    new_node->next = (*head_ref);    

  

    // move the head to point to the new node 

    (*head_ref)    = new_node;

} 

void Search(char *k, pTree tree, char *s[], int *sx) {

    pTree temp;

    char *x=k;

    char same='.';

    int i=0;

    while(tree->strs[i]) {

        if(strlen(tree->strs[i])>2) { 

            s[*sx]=tree->strs[i];

            *sx+=1;

            //printf("  %s\n", tree->strs[i]);

        } 

        i+=1; 

    }

    while(x[0]) {

        if(tree->child[x[0]-'a']) {

            if(same!=x[0]) {

                Search(x+1, tree->child[x[0]-'a'], s, sx);

            }

        }

        same=x[0];

        x+=1;

    }

}

char *keyof(char *word) {

    char buf[100];

    int  count[26]={0,};

    int i, j; 

    i=0;

    while(word[i]!=0) { 

        j=word[i]|32;

        if(j>='a') { 

            count[j-'a']+=1;

        } 

        i+=1; 

    }

    j=0;

    for(i=0;i<26;i+=1) {

        while(count[i]>0) {

            buf[j]='a'+i;

            j+=1;

            count[i]-=1;

        }

    }

    buf[j]=0;

    return strdup(buf);     

}

void printStringTables(char *w, char *s[], int n) {

    int i, j;

    char *t;

    for(i=1;i<n;i+=1) {

        t=s[i];

        j=i;

        while(j>0&&strcmp(s[j-1],t)>0) { 

            s[j]=s[j-1];

            j-=1; 

        }

        s[j]=t;

    }

    printf("단어 %s\n", w);

    for(i=0;i<n;i+=1) {

        if(strcmp(w,s[i])!=0) {

            printf("%s\n", s[i]);

        }

    }

}

int main() {

    FILE *f1;

    pTree  root;

    pPair wpair=NULL;

    char buf[100];

    char *stbl[3000]={0,};

    int sx=0;

    int i, maxx=0;

    f1=fopen("words.txt", "r");

    if(f1==NULL) {

        printf("words.txt파일을 읽을 수 없습니다.\n");

        return 1;

    }

    fgets(buf, 100, f1);

    while(!feof(f1)) {

        i=0;

        while(buf[i]!=0 && buf[i]!='\n') { i+=1; }

        buf[i]=0;

        push(&wpair, keyof(buf), strdup(buf));

        fgets(buf, 100, f1);

    }

    fclose(f1);

    //printList(wpair);

    //printf("\n\n"); getchar();

    // Sort pairs

    MergeSort(&wpair);

    root=(pTree)calloc(sizeof(treeNode), 1);

    insertWords(wpair, root);

    f1=fopen("words.txt", "r");

    if(f1==NULL) {

        printf("words.txt파일을 읽을 수 없습니다.\n");

        return 1;

    }

    fgets(buf, 100, f1);

    while(!feof(f1)) {

        i=0;

        while(buf[i]!=0 && buf[i]!='\n') { i+=1; }

        buf[i]=0;

        sx=0;

        Search(keyof(buf), root, stbl, &sx);

        if(sx>1) {

            printStringTables(buf, stbl, sx);

        }

        if(sx>maxx) { maxx=sx; }

        fgets(buf, 100, f1);

    }

    printf("maxx=%d\n", maxx);

    fclose(f1);

    return 0;

}