1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
// 个人倾向于使用数组形式的字典树,动态节点类型不好debug
//对于字符串比较多的要统计个数的，map被卡的情况下，直接用字典树
//很多题都是要用到节点下标来表示某个字符串
const int maxn =2e6+5;//如果是64MB可以开到2e6+5，尽量开大
int sum[maxn]; // 这个在此??
int tree[maxn][30]; // tree[i][j]表示节点i的第j个儿子的节点编号
bool flagg[maxn]; // 表示以该节点结尾是一个单词,换句话说,`flagg[i]==1`表示至少存在一个单词,其结尾节点是i
int tot;//总节点数
// 至于参数,之后也会考虑换成string 类型

// insert_函数几乎不会发生变化,其主要维护 tot,tree[][],sum[],flagg[]
void insert_(char *str)
{
   int  len=strlen(str);
   int root=0;
   for(int i=0;i<len;i++)
   {
       int id=str[i]-'0';
       if(!tree[root][id]) tree[root][id]=++tot;
       sum[tree[root][id]]++; //记录节点访问次数
       root=tree[root][id];
   }
   flagg[root]=true;
}

/* 此函数表示是否存在前缀为str的单词 */
bool find_(char *str)//查询操作，按具体要求改动
{
    int len=strlen(str);
    int root=0;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(!tree[root][id]) return false;
        root=tree[root][id];
    }
    return true;
}

/* 此函数返回存在前缀str的单词的个数 */
int find_2(char *str)
{
    int len=strlen(str);
    int root=0;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'a';
        if(!tree[root][id]) return 0;
        root=tree[root][id];
    }
    return sum[root];//返回当前字符串结尾节点的访问次数，也就是作为前缀的出现次数
}

/* 此函数返回是否存在单词str */
bool find_3(char *str)
{
    int len=strlen(str);
    int root=0;
    for(int i=0;i<len;i++)
    {
        int id=str[i]-'a';
        if(!tree[root][id]) return true;//该单词没有出现过
        root=tree[root][id];
    }
    if(flagg[root]) return false;//出现过，不再算贡献
    else return true;
}

void init()//最后清空，节省时间
{
    for(int i=0;i<=tot;i++)
    {
       flagg[i]=false;
       for(int j=0;j<10;j++)
           tree[i][j]=0;
    }
   tot=0;//RE有可能是这里的问题
}