trie全wa求调
查看原帖
trie全wa求调
757625
Christins楼主2023/11/17 14:08
#include <bits/stdc++.h> 

using i64 = long long;

const int N = 1010;
int son[N][N * 5][26], cnt[N][N * 5];
int idx;

void insert(std::string s, int id) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!son[id][p][u]) son[id][p][u] = ++idx;
        p = son[id][p][u];
    }
    cnt[id][p]++;
}

bool query(std::string s, int id) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!son[id][p][u]) return false;
        p = son[id][p][u];
    }
    return true;
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    for (int i = 0; i < n; i++) {
        int L;
        std::cin >> L;
        idx = 0;
        for (int j = 0; j < L; j++) {
            std::string s;
            std::cin >> s;
            insert(s, i);
        }
    }

    int m;
    std::cin >> m;

    std::vector<std::vector<int>> ans(m);
    for (int j = 0; j < m; j++) {
        std::string s;
        std::cin >> s;

        for (int i = 0; i < n; i++) {
            if (query(s, i)) {
                ans[j].push_back(i + 1);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < ans[i].size(); j++) {
            if (j) std::cout << " " << ans[i][j];
            else std::cout << ans[i][j];
        }
        std::cout << "\n";
    }

    return 0;
}
2023/11/17 14:08
加载中...