字典树 ———trie树

作用：快速地对字符串进行查找和存储

存储字符串

根节点开始 (p=0) ，判断有没有该类字符，有就向下，没有就添加叶节点，依次存储，把所有结尾点标记一下

void insert_(string s){//存储字符串 
    int p=0;
    for(int i=0;i<s.size();i++){
        int c = s[i]-'a';
        if(!trie[p][c]) trie[p][c]=++k;//计算节点数 
        p = trie[p][c];
    }
    cnt[p]=1;//在字符串尾部标记

} 

查询是否存在这个字符串

bool search_1(string s){//查询是否存在这个字符串 
    int p=0;
    for(int i=0;i<s.size();i++){
        int c = s[i]-'a';
        if(!trie[p][c]) return 0;//没有这条边，即不存在这个字符串 
        p=trie[p][c];
    }
    return cnt[p];//判断字符串是否在p点结束(ab和 abc) 
}   

查询是否有字这个符串的前驱字符串

bool search_2(string s){//查询是否有字这个符串的前驱字符串 
    int p=0;
    for(int i=0;i<s.size();i++){
        int c = s[i]-'a';
        if(cnt[p]) return 1;//ab 是 abc 的前驱字符串  
        if(!trie[p][c]) return 0;//没有这条边 
        p=trie[p][c];
    }
    return cnt[p];//相同也算在前驱字符串abc和abc 
}

P2580 于是他错误的点名开始了

#include<bits/stdc++.h>
using namespace std;
map<string ,int>mp;//查询是否重复
const int N=1e5+10; 
int trie[N][26];
int cnt[N];

void insert_(string s){
    int p=0,k=0;
    for(int i=0;i<s.size();i++){
        int c = s[i]-'a';
        if(!trie[p][c]) trie[p][c]=++k;//如果没有该字符串就添加叶节点 
        p = trie[p][c]; 
    }
    cnt[p] = 1;//在字符串结尾做标记 
}

string search_(string s){
    int p=0;
    for(int i=0;i<s.size();i++){
        int c = s[i]-'a';
        if(!trie[p][c]) return "WRONG";
        p=trie[p][c];
    }
    if(cnt[p]==1) return "OK";
    else return"WRONG";
}
int main(){
    int n,m;
    string a,b;
    scanf("%d",&n);
    while(n--){
        cin >> a;
        insert_(a);
    }
    scanf("%d",&m);
    while(m--){
        cin >> b;
        if(!mp[b]) {
            cout<<search_(b)<<endl;
        }
        else cout<<"REPEAT"<<endl;
        mp[b]=1;
    }
    return 0;
}

What Are You Talking About