a181. 逆逆向思考＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2011-07-12 20:50:21| 人1,051| 回0 | 上一篇 | 下一篇

a181. 逆逆向思考

推 0 收藏 0 0 站台

a181. 逆逆向思考

容：

Trie，又查找或，是一形，是一哈希的。典型用是用於和排序大量的字元串（但不限於字元串），

所以常被搜索引擎系用於文本。它的是：最大限度地少的字元串比，查效率比哈希表高。

以上料引用自基百科

在想你模出一的 Trie

是一 Trie 的例子：

在 Trie 中，保存了 A、to、tea、ted、ten、i、in、inn 8 字元串，用 8 位元（不包括指用的空）。

怕有人因器, 排版掉

例出 :

入明：

有多料,

第一行有一字 N, 代表有 N 字串

每字串度不超 100,0000 字元度

所涵的字元 ASCII 33 ~ 127 (可示字元, 除了空白 32 外)

×　不 N 的, 是希望你用 linked list 做（用建 or 列, 也是OK）

×　不用心的(用做的)

×　得用free();

出明：

於每一

整 Trie 出

按照 ASCII 由小排到大

情考例出

例入：

8 A to tea ted ten i in inn 10 / /7 /? /7g G ( ({ (n /?J /)

例出：

[ ][A] [i][n][n] [t][e][a] [d] [n] [o] [ ][(][n] [{] [/][)] [7][g] [?][J] [G]

提示：

ZeroJudge 的主, 果真是步了, 原本深度 10 就 stack overflow

每想到在出到 20 , 仍然不 overflow

所以在出到深度 100 , 你家的主, 也差不多 10 , 就吃 RE 了

那你要怎呢 ?

出：

Trie (管理：morris1028)

作法 : Trie + 非的作

/**********************************************************************************/
/* Problem: a181 "逆逆向思考" from Trie                                     */
/* Language: C                                                                   */
/*nbsp; 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;
}