Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

a181. 逆逆向思考

內容 ：

輸入說明 ：

輸出說明 ：

範例輸入 ：

範例輸出 ：

提示 ：

出處 ：

/**********************************************************************************/
/*  Problem: a181 "逆逆向思考" from Trie                                     */
/*  Language: C                                                                   */
/*  Result: AC (1780ms, 25368KB) on ZeroJudge                                     */
/*  Author: morris1028 at 2011-07-11 19:15:03                                     */
/**********************************************************************************/


#include<stdio.h>
#include<stdlib.h>
typedef struct TrieNode    {
    char c;
    struct TrieNode *kid, *peer;
}TrieNode;
typedef struct Trie    {
    struct TrieNode *root;
}Trie;
typedef struct Stack {
    struct Stack *prev;
    struct TrieNode *now, *curr;   
    int dv;
    char work;
}Stack;

void Trieinit(Trie*);
void InsTrie(Trie*, char s[]);
void TriePrint(TrieNode*, int);

void Trieinit(Trie *tree) {
    tree->root = (TrieNode*)malloc(sizeof(TrieNode));
    tree->root->c = ' ';
    tree->root->kid = tree->root->peer = NULL;
}
void TriePrint(TrieNode *now, int dv) {
    Stack *stack, *temp;
    stack = (Stack*)malloc(sizeof(Stack));
    stack->prev = NULL, stack->now = now, stack->dv = dv, stack->work = 0;
    int a;
    char flag = 0, flag2;
    while(stack != NULL) {
        if(stack->work == 0) {           
            if(flag == 1) {
                for(a = 0, flag = 0; a < stack->dv; a++)
                    printf("   ");
            }
            stack->curr = stack->now->kid, stack->work = 1;
            printf("[%c]", stack->now->c);

        }           
        flag2 = 0;
        while(stack->curr != NULL) {
            temp = (Stack*)malloc(sizeof(Stack));
            temp->now = stack->curr, temp->prev = stack, temp->dv = stack->dv+1;
            temp->work = 0;
            stack->curr = stack->curr->peer;
            stack = temp, flag2 = 1;
            break;
        }
        if(flag2) continue;
        if(stack->now->kid == NULL)    flag = 1, puts("");
        temp = stack->prev, free(stack->now), free(stack), stack = temp;
    }
}
void InsTrie(Trie *tree, char s[]) {
    TrieNode *curr = tree->root, *prev = NULL, *temp, *p;
    int a;
    for(a = 0; s[a]; a++) {
        p = curr, curr = p->kid, prev = NULL;
        while(curr != NULL && curr->c < s[a]) {
            prev = curr, curr = curr->peer;
        }
       
        if(curr == NULL) {
            temp = (TrieNode*)malloc(sizeof(TrieNode));
            temp->c = s[a], temp->kid = temp->peer = NULL;
            if(prev == NULL)    p->kid = temp;
            else    prev->peer = temp;
            curr = temp;
        }
        else {
            if(curr->c == s[a])    {continue;}
            temp = (TrieNode*)malloc(sizeof(TrieNode));
            temp->c = s[a], temp->kid = NULL;
            if(curr == p->kid)    p->kid = temp, temp->peer = curr;
            else    prev->peer = temp,    temp->peer = curr;
            curr = temp;
        }
    }
}

main() {
    int N;
    char s[1000001];
    while(scanf("%d", &N) == 1) {
        Trie Tree;
        Trieinit(&Tree);
        getchar();
        while(N--)
            gets(s), InsTrie(&Tree, s);
        TriePrint(Tree.root, 0);
    }
    return 0;
}