学步园

用到tire树；

基础应用

 这里讲的挺详细的 点击打开链接

#include<cstdio>
#include<cstring>
#include<iostream>
#define max 20
using namespace std;
char  w[6];
struct node{
    bool a;
    int chile[26];
    int q;//前缀出现次数
    node(){
        q=false;
        q=0;
        memset(chile,0,sizeof(chile));
    }
}t[500000];

int sz=1;
void insert(char *w)
{
    int len=strlen(w);
    int s=0;
    for(int i=0;i<len;i++)
    {
        int y=w[i]-'a';
        if(t[s].chile[y]==0)
        {
            t[s].chile[y]=sz++;
        }
        s=t[s].chile[y];//下一个结点
        t[s].q++;
    }
    t[s].a=1;
}

int show(char *w)
{
    int len=strlen(w);
    int s=0;
    for(int i=0;i<len;i++)
    {
        int y=w[i]-'a';
        if(t[s].chile[y]==0)
            return 0;
        s=t[s].chile[y];
    }
    return t[s].q;
}
int main()
{
    char s[50];
    while(gets(s))
    {
        int len=strlen(s);
        if(len==0) break;
        insert(s);
    }
    while(gets(s))
    {
        printf("%d\n",show(s));
    }
    return 0;
}