Trie树全是输出太短
查看原帖
Trie树全是输出太短
684191
SleepWithMiku楼主2023/11/22 14:35

本地和在线IDE都测得没有问题, 没有多输出空格

#include <bits/stdc++.h>
using namespace std;
int read(){
    int x = 0, f = 1; char c = getchar();
    while(c > '9' || c < '0'){ if(c == '-') f = -1; c = getchar(); }
    while(c <= '9' && c >= '0'){ x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}
int n, m;
int nxt[500007][26], idx;
bitset<1001> b[500007];
void insert(int s, string a){
    int p = 0;
    for(int i = 0; i < a.size(); i ++){
        int k = a[i] - 'a';
        if(!nxt[p][k]){ nxt[p][k] = ++ idx; }
        p = nxt[p][k];
    }
    b[p][s] = 1;
}
void find(string a){
    int p = 0;
    for(int i = 0; i < a.size(); i ++){
        int k = a[i] - 'a';
        if(!nxt[p][k]){ puts(""); return; }
        p = nxt[p][k];
    }
    bool flag = 0;
    for(int i = 1; i <= n; i ++)
        if(b[p][i]){
            if(!flag) {cout << i; flag = 1;}
            else cout << " " << i;
        }
    puts("");
}
signed main()
{
    n = read();
    for(int i = 1; i <= n; i ++){
        int l = read(); string a;
        for(int j = 1; j <= l; j ++){
            cin >> a;
            insert(i, a);
        }
    }
    m = read();
    string a;
    for(int i = 1; i <= m; i ++){
        getline(cin, a);
        find(a);
    }
    return 0;
}
2023/11/22 14:35
加载中...