题意:给你一些单词,要你统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。
裸Tire~,上模板:
Code:
#include <cstdio> #include <cstring> using namespace std; const int maxn = 500000; const int maxw = 20; struct node { bool f; //是否是单词 int child[26]; //是否出现字母 int cnt; //前缀出现次数 int acnt; //单词出现次数 node() { f=false; cnt = 0; acnt = 0; memset(child, 0, sizeof(child)); } } T[maxn]; char word[maxw]; int sz =1; //结点总数 void insert(char* s) { int i, j, pos; int len = strlen(s); int u = 0; for(i=0; i<len; ++i) { pos = s[i]-'a'; if(0 == T[u].child[pos]) { //结点不存在 T[u].child[pos] = sz++; //新建结点 } u = T[u].child[pos]; //往下走 T[u].cnt++; } T[u].f = 1; T[u].acnt++; } int find(char* s) { int len = strlen(s); int i, pos; int u = 0; for(i=0; i<len; ++i) { pos = s[i] -'a'; if(0 == T[u].child[pos]) { return 0; } u = T[u].child[pos]; //往下走 } return T[u].cnt; } int main() { char word[maxw]; while(gets(word)) { int len = strlen(word); if(0 == len) break; insert(word); } while(gets(word)) { printf("%d\n", find(word)); } return 0; }