字典树爆炸(map已过)
查看原帖
字典树爆炸(map已过)
615931
Qianmo_su楼主2023/3/2 20:36
#include <bits/stdc++.h>
using namespace std;

const int N = 3e6+10;
int t[N][65],cnt[N],id = 1,n,m,vis[N];
string str;

//字符转化成为ASCII码
int getnum(char x)
{
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
//建树
void insert(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        if(t[p][x] == 0) t[p][x] = id++;
        p = t[p][x];
        cnt[p]++;
    }
}
//查询
void find(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        //没有找到
        if(t[p][x] == 0) {cout << "WRONG";return ;}
        p = t[p][x];
    }
    int tx = cnt[p];
    if(tx && vis[p] == 0) {cout << "OK" << endl;vis[p]++;}
    else if(tx && vis[p]!=0) cout << "REPEAT" << endl;
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> str;
        insert(str);
    }
    cin >> m;
    for(int i=1;i<=m;i++)
    {
        cin >> str;
        find(str);
    }
}
2023/3/2 20:36
加载中...