题意:
给你多个单词,然后在给你一个字符串s,现在要问你以该字符串s为前缀的单词数目有多少个?
分析:
标准的Trie树应用,我们只需要用树节点的v值表示以树根root到当前节点的路为前缀的单词数即可.
在插入新单词节点的时候,该单词节点路过的所有Trie节点v都要+1.
查询的时候,如果能查到该前缀,直接输出v值,否则输出0.
#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
using namespace std;const int maxn = 1000005;struct node
{int ch[maxn][26];int v[maxn];int sz;void init(){sz=1;memset(ch[0],0,sizeof ch[0]);}int idx(char c){return c-'a';}void insert(char *s){int u=0,n=strlen(s);for(int i=0;i<n;i++){int id=idx(s[i]);if(ch[u][id]==0){ch[u][id]=sz;memset(ch[sz],0,sizeof ch[sz]);v[sz++]=0;}u=ch[u][id];v[u]++;//每个单词经过都要该节点就+1.}}int find(char *s){int u=0,n=strlen(s);for(int i=0;i<n;i++){int id=idx(s[i]);if(!ch[u][id]){return 0;}elseu=ch[u][id];}return v[u];}
}trie;int main()
{trie.init();char s[111];while(gets(s)){if(!s[0])break;trie.insert(s);}while(gets(s)){printf("%d\n",trie.find(s));}
}