Trie树

建立一个字典树，先存入单词，再查找单词，最后输出具有该前缀的单词数量。

#include<cstdio>
#include<cstdlib>

struct node
{
    int cnt;
    int next[26];
} T[10000010];

int t=0;
char str[20];

void Insert(char *s)
{
    int i=0, p=0, temp;
    while(s[i])
    {
        temp=s[i]-'a';
        if(T[p].next[temp]==0)
        {
            t++;
            T[p].next[temp]=t;
        }
        p=T[p].next[temp];
        T[p].cnt++;
        i++;
    }
}

void Query(char *s)
{
    int i=0, p=0, temp;
    while(s[i])
    {
        temp=s[i]-'a';
        if(T[p].next[temp]==0)
        {
            printf("0\n");
            return ;
        }
        p=T[p].next[temp];
        i++;
    }
    printf("%d\n",T[p].cnt);
    return ;
}

int main()
{
    int m, n;
    scanf("%d", &n);
    getchar();
    while(n--)
    {
        gets(str);
        Insert(str);
    }
    scanf("%d", &m);
    getchar();
    while(m--)
    {
        gets(str);
        Query(str);
    }
    return 0;
}

核心代码：

void Insert(char *s)
{
    int i=0, p=0, temp;
    while(s[i])
    {
        temp=s[i]-'a';
        if(T[p].next[temp]==0)
        {
            t++;
            T[p].next[temp]=t;
        }
        p=T[p].next[temp];
        T[p].cnt++;
        i++;
    }
}

先判断是否存在该前缀，如果不存在，就构建新的枝叶。
查找一个就为该枝叶记一次数，表示到该枝叶的前缀个数