统计难题

banana

band

bee

absolute

acm

ba

b

band

abc

2

3

1

0

题目大意：

给定一些单词，然后接下来非常多询问，每组一个字符串T。问你给定的单词中前缀为T的有多少个？

解题思路：

先依照给定的单词建一棵Trie树。记录值。然后每次查询就可以。

解题代码：

#include <iostream>

#include <cstring>

#include <string>

using namespace std;

const int maxn=500000;

int tree[maxn][30];

int val[maxn],cnt;

void insert(string st){

    int s=0;

    for(int i=0;i<st.length();i++){

        if( tree[s][st[i]-'a']==0 ) tree[s][st[i]-'a']=++cnt;

        s=tree[s][st[i]-'a'];

        val[s]++;

    }

}

int query(string st){

    int s=0;

    for(int i=0;i<st.length();i++){

        s=tree[s][st[i]-'a'];

        if(s==0) return 0;

    }

    return val[s];

}

int main(){

    string st;

    while( getline(cin,st) && st.length()>0 ){

        insert(st);

    }

    while(getline(cin,st)){

        cout<<query(st)<<endl;

    }

    return 0;

}