统计难题

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)

Total Submission(s): 22291    Accepted Submission(s): 9424

banana

band

bee

absolute

acm

ba

b

band

abc

2

3

1

0

题解：建一颗字典树，然后查询出现的次数即可了。

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cmath>

#include<vector>

#include<cstring>

#define N 10010

using namespace std;

int n;

char s[N];

typedef struct tire {

    int num;

    struct tire *net[26];

}*Tire;

void Init(Tire &p) {

    p=(Tire)malloc(sizeof(tire));

    p->num=0;

    for(int i=0; i<26; i++) {

        p->net[i]=NULL;

    }

}

void CreatTire(Tire &p,char s[]) {

    int i=0;

    Tire q=p;

    while(s[i]) {

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

        if(q->net[nx]==NULL) {

            Init(q->net[nx]);

            q->net[nx]->num=1;

        } else {

            q->net[nx]->num++;

        }

        q=q->net[nx];

        i++;

    }

}

int Serch(Tire p,char s[]) {

    int i=0;

    Tire q=p;

    while(s[i]) {

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

        if(q->net[nx]==NULL)return 0;

        q=q->net[nx];

        i++;

    }

    return q->num;

}

int main() {

    //freopen("test.in","r",stdin);

    Tire p;

    Init(p);

    while(gets(s)!=NULL&&s[0]!='\0') {

        CreatTire(p,s);

    }

    while(~scanf("%s",s)) {

        printf("%d\n",Serch(p,s));

    }

    return 0;

}