/*

  trie tree的储存方式：将字母储存在边上，边的节点连接与它相连的字母

  trie[rt][x]=tot:rt是上个节点编号，x是字母，tot是下个节点编号

*/

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#define maxn 2000010

using namespace std;

int tot=,n;

int trie[maxn][];

//bool isw[maxn];查询整个单词用

void insert(char *s,int rt)

{

    for(int i=;s[i];i++)

    {

        int x=s[i]-'a';

        if(trie[rt][x]==)//现在插入的字母在之前同一节点处未出现过

        {

            trie[rt][x]=++tot;//字母插入一个新的位置，否则不做处理

        }

        rt=trie[rt][x];//为下个字母的插入做准备

    }

    /*isw[rt]=true;标志该单词末位字母的尾结点，在查询整个单词时用到*/

}

bool find(char *s,int rt)

{

    for(int i=;s[i];i++)

    {

        int x=s[i]-'a';

        if(trie[rt][x]==)return false;//以rt为头结点的x字母不存在，返回0

        rt=trie[rt][x];//为查询下个字母做准备

    }

    return true;

    //查询整个单词时，应该return isw[rt]

}

char s[];

int main()

{

    tot=;

    int rt=;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        cin>>s;

        insert(s,rt);

    }

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        cin>>s;

        if(find(s,rt))printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

数组模拟

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

int trie[][],len,root,tot,sum[];

bool p;

int n,m;

char s[];

void insert()

{

    len=strlen(s);

    root=;

    for(int i=;i<len;i++)

    {

        int id=s[i]-'a';

        if(!trie[root][id]) trie[root][id]=++tot;

        sum[trie[root][id]]++;//前缀后移一个位置保存

        root=trie[root][id];

    }

}

int search()

{

    root=;

    len=strlen(s);

    for(int i=;i<len;i++)

    {

        int id=s[i]-'a';

        if(!trie[root][id]) return ;

        root=trie[root][id];

    }//root经过此循环后变成前缀最后一个字母所在位置的后一个位置

    return sum[root];//因为前缀后移了一个保存，所以此时的sum[root]就是要求的前缀出现的次数

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        cin>>s;

        insert();

    }

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        cin>>s;

        printf("%d\n",search());

    }

}

数组模拟

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<string.h>

#include<string>

using namespace std;

const int max_=1e6+;

int trie[max_][];

int tot=;

char s[max_];

int sum[max_];

void insert(char str[])

{

    //int len=str.size();

    int rt=;

    for(int i=;str[i];i++)

    {

        int k=str[i]-'a';

        if(!trie[rt][k])

            trie[rt][k]=++tot;

            sum[trie[rt][k]]++;

        rt=trie[rt][k];

    }

}

int find(char str[])

{

    //int len=strlen(str);

    int rt=;

    for(int i=;str[i];i++)

    {

        int k=str[i]-'a';

        if(!trie[rt][k])

            return ;

        rt=trie[rt][k];

    }

    return sum[rt];

}

int main()

{

    /*std::ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);*/

    //string str;

    while(gets(s))

    {

        //cout<<str<<endl;

        if(s[]=='\0')

            break;

        insert(s);

    }

    while(scanf("%s",s)!=EOF)

    {

       // printf("ok\n");

        int ant=find(s);

        printf("%d\n",ant);

    }

}

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<string.h>

#include<sstream>

using namespace std;

const int max_=2e4+;

int tot;

int trie[max_][];

bool book[max_];

void insert(string str)

{

    int len=str.size();

    int rt=;

    for(int i=;i<len;i++)

    {

        int k=str[i]-'a';

        if(!trie[rt][k])

            trie[rt][k]=++tot;

        rt=trie[rt][k];

    }

    book[rt]=;

}

bool find_(string str)

{

    int len=str.size();

    int rt=;

    for(int i=;i<len;i++)

    {

        int k=str[i]-'a';

        if(!trie[rt][k])

            return ;

        rt=trie[rt][k];

    }

   if(book[rt])

    return ;

   else

    return ;

}

int main()

{

    ios::sync_with_stdio(false);

    string str1,str2;

    while(getline(cin,str1))

    {

        if(str1=="#")

            break;

        tot=;

        int ant=;

        memset(trie,,sizeof(trie));

        memset(book,,sizeof(book));

        stringstream ss(str1);

        while(ss>>str2)

        {

            //cout<<ss<<endl;

            if(!find_(str2))

            {

                ant++;

                insert(str2);

            }

        }

        printf("%d\n",ant);

    }

}