55分,求助
查看原帖
55分,求助
1003111
idle_person楼主2023/8/21 18:30

我把每个短文都放到一个单独的字典树里,查找的时候分开查,这样为什么会wa呀。

#include <bits/stdc++.h>
using namespace std;
#define MAX int(7e3+7)
#define inf INT_MAX
#define fi first
#define se second
typedef long long ll;
//const int p = 998244353;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
//typedef vector<p> vp;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<pl> vp;
int n, m, l;
int tr[2000][MAX][27];
int num[2000][MAX];
int cnt;
string s;


void insert(string& s, int k) {
    int p = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        int ch = s[i] - 'a';
        if (!tr[k][p][ch])tr[k][p][ch] = (++cnt);
        p = tr[k][p][ch];
    }
    num[k][p] = 1;
}

bool ask(string& s, int k) {
    int p = 0;
    for (int i = 0; i < (int)s.size(); ++i) {
        int ch = s[i] - 'a';
        if (!tr[k][p][ch])return false;
        p = tr[k][p][ch];
    }
    return num[k][p];
}

void solve() {
    cnt = 0;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> l;
        for (int j = 0; j < l; ++j) {
            cin >> s;
            insert(s, i);
        }
    }
    cin >> m;
    for (int i = 0; i < m; ++i) {
        cin >> s;
        for (int j = 0; j < n; ++j)
            if (ask(s, j)) {
                cout << j + 1 << ' ';
            }
        cout << '\n';
    }
}



int main() {
    ios::sync_with_stdio(false);//int T;
    //for (cin >> T;T--;)
    solve();
    return 0;
}
2023/8/21 18:30
加载中...