All Too long 求助,可过样例
查看原帖
All Too long 求助,可过样例
416242
New_hope楼主2024/5/25 16:43
#include <bits/stdc++.h>
#define _ 500007
using namespace std;

int n, m;
char s[40];

struct node
{
  int son[40];
  vector <int> v;
  void init() {
    memset (son, 0, sizeof son);
    v.clear();
  }
} tr[_];
struct trie
{
  int tot;
  void init() { tot = 0; }
  void insert(int num) {
    int n = strlen(s + 1), p(0);
    for (int i(1); i <= n; i ++) {
      int t = s[i] - 'a';
      if (!tr[p].son[t]) {
        tr[p].son[t] = ++ tot;
      } p = tr[p].son[t];
      if (i == n) tr[p].v.push_back(num);
    }
  }
  vector <int> find() {
    int n = strlen(s + 1), p(0);
    for (int i(1); i <= n; i ++) {
      int t = s[i] - 'a';
      if (!tr[p].son[t]) return tr[p].v;
      p = tr[p].son[t];
    } return tr[p].v;
  }
} t;
int main()
{
  scanf ("%d", &n);
  t.init();
  for (int i(1); i < 30; i ++) tr[i].init();
  for (int i(1); i <= n; i ++) {
    int L; scanf ("%d", &L);
    for (int j(1); j <= L; j ++) {
      scanf ("%s", s + 1);
      t.insert(i);
    }
  }
  scanf ("%d", &m);
  for (int i(1); i <= m; i ++) {
    scanf ("%s", s + 1);
    vector <int> r = t.find();
    if (!r.size()) {
      printf ("\n");
      continue;
    }
    int l = unique (r.begin(), r.end()) - r.begin();
    printf ("%d", r[0]);
    for (int i(1); i < l; i ++) {
      printf (" %d", r[i]);
    } printf ("\n");
  }


  return 0;
}
2024/5/25 16:43
加载中...