字典树模板

sdut 2828 字典树

Description

遇到单词不认识怎么办? 查字典啊，已知字典中有n个单词，假设单词都是由小写字母组成。现有m个不认识的单词，询问这m个单词是否出现在字典中。

Input

含有多组测试用例。

第一行输入n，m (n>=0&&n<=100000&&m>=0&&m<=100000)分别是字典中存在的n个单词和要查询的m个单词.

紧跟着n行，代表字典中存在的单词。

然后m行，要查询的m个单词

n=0&&m=0 程序结束

数据保证所有的单词都是有小写字母组成，并且长度不超过10

Output

若存在则输出Yes，不存在输出No .

Sample

Input

3 2

aab

0 0

Output

Yes

等有空再补充链表的做法

#include <bits/stdc++.h>

using namespace std;
char s[20];
int trie[500010][26];        //数组开的很玄学，大一点TLE小一点RTE
int cc[500010];        //用来证明单词存在
int f = 1;

void in_sert(){
    int k = strlen(s);
    int p = 0;
    for(int i = 0; i<k; i++){
        int c = s[i] - 'a';
        if(!trie[p][c]){
            memset(trie[f], 0, sizeof(trie[f]));        //能用到的时候再初始化，应该能省点时间？
            trie[p][c] = f;
            f++;
        }
        p = trie[p][c];    //p指向下一个字母的储存位置
    }
    cc[p] = 1;    //标记单词收尾处
}

bool se_arch(){
    int k = strlen(s);
    int p = 0;
    for(int i = 0; i<k; i++){
        int c = s[i] - 'a';
        if(trie[p][c] == 0) return 0；    //说明下一个字母不在树中，结束
        p = trie[p][c];
    }
    if(!cc[p]) return 0;        //在树中不是完整的单词，例如树中保存aaa,查询aa
    else return 1;
}

int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m)&&(n||m)){
        getchar();
        memset(trie[0], 0, sizeof(trie[0]));
        memset(cc, 0, sizeof(cc));
        f = 1;    //用来指示字母保存的位置
        while(n--){
            scanf("%s", s);
            in_sert();
        }
        while(m--){
            scanf("%s", s);
            int t = se_arch();
            if(t) printf("Yes
");
            else printf("No
");
        }
    }
    return 0;
}

sdut 3039 迷之好奇

Description

FF得到了一个有n个数字的集合。不要问我为什么，有钱，任性。<o:p></o:p>

FF很好奇的想知道，对于数字x，集合中有多少个数字可以在x前面添加任意数字得到。<o:p></o:p>

如，x = 123，则在x前面添加数字可以得到4123，5123等。<o:p></o:p>

Input

多组输入。

对于每组数据<o:p></o:p>

首先输入n(1<= n <= 100000)。<o:p></o:p>

接下来n行。每行一个数字y(1 <= y <= 100000)代表集合中的元素。<o:p></o:p>

接下来一行输入m(1 <= m <= 100000),代表有m次询问。<o:p></o:p>

接下来的m行。<o:p></o:p>

每行一个正整数x(1 <= x <= 100000)。<o:p></o:p>

Output

对于每组数据，输出一个数字代表答案。

<o:p></o:p>

Sample

Input

Output

1
0
1

Hint

一开始想的是如果单词刚好相等输出次数就减1，交上去wa,后来想起可能输入多个相同的单词，又建了一个vis数组统计单词出现次数。

#include <bits/stdc++.h>

using namespace std;
int trie[500010][10];
int cc[500010];     //储存字母经过的次数
int vis[500010];    //储存单词结尾
char s[15];
int k;

void in_sert(){
    int i = strlen(s)-1;
    int p = 0;
    for(; i>=0; i--){
        int c = s[i] - '0';
        if(!trie[p][c]){
            memset(trie[k], 0, sizeof(trie[k]));
            trie[p][c] = k++;
        }
        p = trie[p][c];
        cc[p]++;
    }
    vis[p]++;
}

int se_arch(){
    int i = strlen(s)-1;
    int p = 0;
    for(; i>=0; i--){
        int c = s[i] - '0';
        if(!trie[p][c]) return 0;
        p = trie[p][c];
    }
    if(vis[p]) return cc[p]-vis[p];     //减掉与被查询词刚好相等的次数
    else return cc[p];
}

int main()
{
    int n, m;
    while(~scanf("%d", &n)){
        k = 1;
        memset(trie[0], 0, sizeof(trie[0]));
        memset(cc, 0, sizeof(cc));
        memset(vis, 0,sizeof(vis));
        while(n--){
            scanf("%s", s);
            in_sert();
        }
        scanf("%d", &m);
        while(m--){
            scanf("%s", s);
            printf("%d
", se_arch());
        }
    }
    return 0;
}