首页 > 代码库 > 统计难题

统计难题

2024-09-19 21:15:00   219人阅读

OJ题号：HDU1251

思路：

Trie，插入时新增一个附加值cnt记录经过当前结点的字符串个数，每插入一个字符串时就将每个结点+1。 每次询问时，如果遇到不存在的结点，就说明没有以该字符串为前缀的字符串，直接跳出。 如果找到了当前字符串的末尾结点，就将当前结点的cnt值累加到ans中。

 1 #define maxnode 1000000
 2 #define maxlength 10+1
 3 #define sigma_size 26
 4 #include<cstdio>
 5 #include<cstring>
 6 int ans;
 7 struct Trie {
 8     int ch[maxnode][sigma_size];
 9     int val[maxnode],cnt[maxnode];
10     int sz;
11     int idx(char c) {
12         return c-‘a‘;
13     }
14     Trie() {
15         sz=1;
16         memset(ch[0],0,sizeof(ch[0]));
17     }
18     void insert(char *s) {
19         int u=0,n=strlen(s);
20         for(int i=0;i<n;i++) {
21             int c=idx(s[i]);
22             if(!ch[u][c]) {
23                 memset(ch[sz],0,sizeof(ch[sz]));
24                 cnt[sz]=val[sz]=0;
25                 ch[u][c]=sz++;
26             }
27             u=ch[u][c];
28             cnt[u]++;
29         }
30         val[u]=1;
31     }
32     void ask(char *s) {
33         int u=0,n=strlen(s);
34         for(int i=0;i<n;i++) {
35             int c=idx(s[i]);
36             if(!ch[u][c]) {
37                 return;
38             }
39             u=ch[u][c];
40         }
41         ans+=cnt[u];
42     }
43 };
44 Trie trie;
45 int main() {
46     char s[maxlength];
47     while(gets(s)) {
48         if(!s[0]) break;
49         trie.insert(s);
50     }
51     while(gets(s)!=NULL) {
52         ans=0;
53         trie.ask(s);
54         printf("%d\n",ans);
55     }
56     return 0;
57 }

注：本随笔整理自QQ空间旧文。发布时间为2017年3月14日。

查看原文

统计难题


联系
我们