点这里看题面

这题我们发现他要我们求以一个字符串作为前缀的字符串的个数,而Trie树刚好就是按前缀来建的树。所以我们刚好可以在新增字符串的时候统计一下,用sum[i]表示以标号为i的节点作为终止节点的这个字符串作为前缀,总共有多少个字符串,然后在我们一层一层访问的时候没访问一次加一次就好了。这里可能没讲清楚,可以到代码里看。

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
int n,m,tot;char s[20];
int sum[maxn],trie[maxn][26];
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void add(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int ch=s[i]-'a';
        if(!trie[p][ch])trie[p][ch]=++tot;
        p=trie[p][ch];sum[p]++;
    }
}
int find(char *s){
    int len=strlen(s),p=0;
    for(int i=0;i<len;i++){
        int ch=s[i]-'a';
        if(!trie[p][ch])return 0;
        p=trie[p][ch];
    }return sum[p];
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        scanf("%s",s),add(s);
    m=read();
    for(int i=1;i<=m;i++)
        scanf("%s",s),printf("%d\n",find(s));
    return 0;
}

发表评论