字典树

#include<cstdio>
#include<cstring>
#include<algorithm>
#define idx(x) (x-'a')
using namespace std;
int n,m;     //输入字符串数    查询次数 
int ant;    //记录当前在哪一层 
struct Node
{
    int v;  //当前有多少个字符串共用这个数组 
    Node *next[26];  //指针数组指向下一层 
    void init()  //清空本层 
    {
        v=0;
        for(int i = 1;i <= 26; i++)
        {
            next[i] = NULL;
        }   
    }
}trie[100000];
void insert(char *str)
{
    Node *p = &trie[0];  //现在执行到的节点 
    int len = strlen(str); 
    for(int i = 0; i < len; i++)
    {
        if(p -> next[idx(str[i])] == NULL)  
        {
            p -> next[idx(str[i])] = &trie[ant]; //如果节点为空则赋值此节点 
            ant++;                      
            trie[ant].init();       //初始化下一层 
            trie[ant-1].v=1;
            p = &trie[ant-1];           
        }
        else
        {
            p->v++;
            p = p -> next[idx(str[i])];  
        }   
    }   
}
int Querylen(char *str)
{
    Node p = trie[0];
    int lenth = 0;
    int l = strlen(str);
    for(int  i = 0; i < l ; i++)
    {
            if(p.next[idx(str[i])] == NULL)  //到此结点无公共前缀 结束循环 
            break;
            else
            {
                lenth++;
                p = *p.next[idx(str[i])];   //向下一层出发 
            }

    }
return lenth;   
}
int main()
{
    char str[20];
    scanf("%d %d",&n,&m);
    trie[ant].init();
    for(int i = 1; i <= n; i++)
    {
        scanf("%s",str);
        insert(str);
    }
    for(int i = 1;i <= m; i++)
    {
        scanf("%s",str);
        printf("%d\n",Querylen(str));
    }
return 0;   
}

示例：