字典树，字典树+dfs，（数组实现），两个例题

Posted on | In |

字典树（数组实现）

学习参考博客。
又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
在这里插入图片描述
添加操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int maxn=50000+500;
int trie[maxn][30],tot=0;
bool flag[5555555];
void insert(string a)
{
    int root=0,id,len=a.length();
    for(int i=0;i<len;i++)
    {
        id=a[i]-'a';
        if(trie[root][id]==0)
        trie[root][id]=++tot;
        root=trie[root][id];
    }
    flag[root]=true;
}

查询操作：

1
2
3
4
5
6
7
8
9
10
11
12
bool search(string a)
{
    int root=0,id,len=a.length();
    for(int i=0;i<len;i++)
    {
        id=a[i]-'a';
        if(trie[root][id]==0)
        return false;
        root=trie[root][id];
    }
    return flag[root];
}

Hat’s Words

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

Output

Your output should contain all the hat’s words, one per line, in alphabetical order.

Sample Input
1
2
3
4
5
6
a
ahat
hat
hatword
hziee
word
Sample Output
1
2
ahat
hatword

题目大意：输入一些字符串，看这些单词中，有没有由其他两个单词构成的复合词并将其输出。
例如“hatword”=“hat”+“word”
思路，对于每一个单词第一位开始进行拆分成两个词，然后分别搜索，都存在时就输出。

AC代码：

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=50000+500;
string b[maxn];
int trie[maxn][30],tot=0;
bool flag[5555555];
void insert(string a)//添加
{
    int root=0,id,len=a.length();
    for(int i=0;i<len;i++)
    {
        id=a[i]-'a';
        if(trie[root][id]==0)
        trie[root][id]=++tot;
        root=trie[root][id];
    }
    flag[root]=true;
}
bool search(string a)//搜索
{
    int root=0,id,len=a.length();
    for(int i=0;i<len;i++)
    {
        id=a[i]-'a';
        if(trie[root][id]==0)
        return false;
        root=trie[root][id];
    }
    return flag[root];
}
int main()
{
    int num=0;
    memset(trie,0,sizeof(trie));
    memset(flag,false,sizeof(flag));
    while(cin>>b[num])
    {
        insert(b[num]);
        num++;
    }
    // cout<<num;
    for(int i=0;i<num;i++)
    {
        for(int j=1;j<b[i].length();j++)//拆分词
        {
            string l=b[i].substr(0,j);
            string r=b[i].substr(j,b[i].size()-1);
            if(search(l)&&search(r))//前后单词都存在时。
            {
                cout<<b[i]<<endl;
                break;
            }
        }
    }
    return 0;
}

例题2：Watto and Mechanism

Watto, the owner of a spare parts store, has recently got an order for the mechanism that can process strings in a certain way. Initially the memory of the mechanism is filled with n strings. Then the mechanism should be able to process queries of the following type: “Given string s, determine if the memory of the mechanism contains string t that consists of the same number of characters as s and differs from s in exactly one position”.

Watto has already compiled the mechanism, all that’s left is to write a program for it and check it on the data consisting of n initial lines and m queries. He decided to entrust this job to you.

Input

The first line contains two non-negative numbers n and m (0 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — the number of the initial strings and the number of queries, respectively.

Next follow n non-empty strings that are uploaded to the memory of the mechanism.

Next follow m non-empty strings that are the queries to the mechanism.

The total length of lines in the input doesn’t exceed 6·105. Each line consists only of letters ‘a’, ‘b’, ‘c’.

Output

For each query print on a single line “YES” (without the quotes), if the memory of the mechanism contains the required string, otherwise print “NO” (without the quotes).

Examples

Input
1
2
3
4
5
6
2 3
aaaaa
acacaca
aabaa
ccacacc
caaac
Output
1
2
3
YES
NO
NO

此题感谢mhr大佬的题解，tql，Or2.
这个题的难点在于用f的标记是否有一个字符不同的过程。

AC代码：

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=300000+500;
int trie[maxn][30];
bool flag[600050];
int tot=0,f,len;
string b;
void insert(string a)//添加基操
{
    int id=0,rt=0,len=a.length();
    for(int i=0;i<len;i++)
    {
        id=a[i]-'a';
        if(trie[rt][id]==0)
        {
            trie[rt][id]=++tot;
        }
        rt=trie[rt][id];
    }
    flag[rt]=true;
}
bool dfs(int pos,int root)//精华所在，pos表示字符串的位置，root表示根节点的位置。
{
    if(pos==len)//递归结束，匹配完毕
    {
        if(flag[root]&&f==0)
        return true;
        else return false;
    }
    int id=b[pos]-'a';
    for(int i=0;i<3;i++)
    {
        if(trie[root][i])//当前节点不为空。
        {
            if(i==id)//如果当前匹配
            {
                if(dfs(pos+1,trie[root][i]))//继续搜索下一节点
                return true;
            }
            else if(f!=0)//f用来标记是否有一个不同的字符，没有出现过就为f=1；
            {
                f=0;//标记一下，证明有一个字符不同
                if(dfs(pos+1,trie[root][i]))。//搜索下一节点
                return true;
                f=1;//搜索当前root的下一个字符，并取消标记（因为没有用到这个节点）。
            }
        }
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string a;
        cin>>a;
        insert(a);
    }
    for(int i=0;i<m;i++)
    {
        f=1;
        cin>>b;
        len=b.length();
        if(dfs(0,0))
        cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
坚持原创技术分享，您的支持也将成为我的动力！
-------------本文结束感谢您的阅读-------------
undefined