Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
思路很简单，前缀数组入门题，对于每个结点，用val数组记录当前字符串为前缀的字符串数量，之后就是插入，查询操作了
代码如下：
#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long const int maxnode = 1000000 ; const int sigma_size = 26; struct Trie { int ch[maxnode][sigma_size]; int val[maxnode]; int sz; Trie() { 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 c = idx(s[i]); if(!ch[u][c]) { memset(ch[sz], 0, sizeof(ch[sz])); val[sz] = 1; ch[u][c] = sz++; } else val[ch[u][c]]++; u = ch[u][c]; } } int find(char *s) { int u = 0, n = strlen(s); for(int i = 0; i < n; i++) { int c = idx(s[i]); if(!ch[u][c]) return 0; else u = ch[u][c]; } return val[u]; } }; Trie trie; int main() { char dic[11], qry[11]; //freopen("input.txt", "r", stdin); while(gets(dic) && strcmp(dic, "") != 0) { // printf("%s\n", dic); trie.insert(dic); } while(gets(qry)) printf("%d\n", trie.find(qry)); return 0; }