/*************************************************************************

    > File Name: Trie.c

    > Author:

    > Mail:

    > Created Time: Tue 11 Dec 2018 03:46:05 PM CST

 ************************************************************************/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

int charmapping[];

void init_charmapping()

{

    for(int i='a';i<='z';i++)

    {

        charmapping[i]=i-'a';

    }

}

const int maxn = ;    //这里假设字符串只出现26个小写字母

const int maxm = ;

struct treenode

{

    bool end;

    struct treenode *next[maxn];

}head;

struct treenode memory[maxm];

int mallocp = ;

void init()

{

    head.end = ;

    for(int i = ;i<maxn;i++) head.next[i] = NULL;

}

treenode* createnew()

{

    treenode *newnode;

    newnode = &memory[mallocp++];

    newnode->end = ;

    for(int i=;i<maxn;i++) newnode->next[i] = NULL;

    return newnode;

}

void update(char *s)

{

    int k = ,temp;

    treenode *t = &head;

    while(s[k])

    {

        temp = charmapping[s[k]];     //找到c字符对应的标号2

        if(!t->next[temp]) t->next[temp] = createnew();

        t = t->next[temp];

        k++;

    }

    t->end = ;

}

bool search(char *s)

{

    int k = ,temp;

    treenode *t = &head;

    while(s[k])

    {

        temp = charmapping[s[k]];

        if(!t->next[temp]) return false;        //已经遍历到最后一个结点

        t = t->next[temp];

        k++;

    }

    if(t->end) return true;

    return false;

}

int main(int argc,char **argv)

{

    //freopen("text.txt","r",stdin);

    init();

    char x[];

    char t;

    while()

    {

        fflush(stdin);

        scanf("%c",&t);

        getchar();

        if(t=='q')

        {

            scanf("%c",&x);

            getchar();

            if(search(x))     printf("匹配成功！\n");

            else printf("匹配失败！\n");

        }

        else if(t=='u')

        {

            scanf("%s",&x);

            getchar();

            update(x);

            printf("更新完毕！\n");

        }

        else if(t=='e')

        {

            printf("退出ing……\n");

            break;

        }

        else

            printf("无效命令！\n");

    }

    return ;

}

/*************************************************************************

    > File Name: Trie_dynamic.cpp

    > Author:

    > Mail:

    > Created Time: Tue 11 Dec 2018 05:23:37 PM CST

 ************************************************************************/

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

using namespace std;

int charmapping[];

void init_charmapping()

{

    for(int i='a';i<'z';i++)

    {

        charmapping[i] = i - 'a';

    }

}

const int maxn = ;

const int maxm = ;

struct treenode

{

    int count;

    treenode *next[maxn];

}head;

void init_trie()

{

    head.count = ;

    for(int i=;i<maxm;i++) head.next[i] = NULL;

}

treenode* createnew()

{

    treenode *newnode;

    newnode = (treenode*)malloc(sizeof(treenode));

    newnode->count = ;

    for(int i=;i<maxn;i++) newnode->next[i] = NULL;

    return newnode;

}

void update(char *s,int num)

{

    int k=,temp;

    treenode *t = &head;

    while(s[k])

    {

        t->count+=num;

        temp = charmapping[s[k]];

        if(!t->next[temp]) t->next[temp] = createnew();

        t = t->next[temp];

        k++;

    }

    t->count+=num;

}

bool search(char *s,int num)

{

    int k = ,temp;

    treenode *t = &head;

    while(s[k])

    {

        temp = charmapping[s[k]];

        if(!t->next[temp] || t->next[temp]->count<num)    return false;

        t = t->next[temp];

        k++;

    }

    int snum = t->count;

    for(int i=;i<maxn;i++) if(t->next[i]) snum -= t->next[i]->count;

    if(snum>=num) return true;

    return false;

}

void erase(char *s,int num)

{

    int k = ,temp;

    treenode *t = &head;

    treenode *t1;

    head.count -= num;

    while(s[k])

    {

        temp = charmapping[s[k]];

        t->next[temp]->count -= num;

        if(t->next[temp]->count==)

        {

            t1 = t->next[temp];

            t->next[temp]=NULL;

            k++;

            break;

        }

        t = t->next[temp];

        k++;

    }

    while(s[k])

    {

        temp = charmapping[s[k]];

        t = t1->next[temp];

        free(t1);

        t1 = t;

        k++;

    }

}

char temp[];

void printall(treenode *tnode,int pos)

{

    int count = tnode->count;

    for(int i=;i<maxn;i++)    if(tnode->next[i]) count -= tnode->next[i]->count;

    for(int i=;i<count;i++) printf("\"%s\"\n",temp);

    for(int i='a';i<='z';i++)

    {

        if(tnode->next[charmapping[i]])

        {

            temp[pos] = i;

            temp[++pos]='\0';

            printall(tnode->next[charmapping[i]],pos);

            temp[--pos]='\0';

        }

    }

}