20分蒟蒻求助

P8306 【模板】字典树

__JiCanDuck__ @ 2023-01-10 14:39:54

#include <cstring>
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

const int kMaxN = 3e6 + 1;

int n, t, a[kMaxN][60], cnt, ans, Cnt[kMaxN], q;
string s;

int zhuan(char x) {
  if (x >= 'A' && x <= 'Z')
    return x - 'A';
  else if (x >= 'a' && x <= 'z')
    return x - 'a' + 26;
  return -1;
}

void Add(string s) {
  int p = 0, ok = 0, l = s.size();
  for (int i = 0; i < l; i++) {
    int c = zhuan(s[i]);
    if (!a[p][c]) {
      a[p][c] = ++cnt;
    }
    p = a[p][c];
    Cnt[p]++;
  }
}

int check(string s) {
  int p = 0, ok = 0, l = s.size();
  for (int i = 0; i < l; i++) {
    int c = zhuan(s[i]);
    if (!a[p][c]) {
      return 0;
    }
    p = a[p][c];
  }
  return Cnt[p];
}

int main() {
  ios :: sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (cin >> q; q; q--) {
    cin >> n >> t;
    for (int i = 1; i <= cnt; i++) {
      for (int j = 1; j <= 52; j++) {
        a[i][j] = 0;
      }
    }
    for (int i = 1; i <= cnt; i++) {
      Cnt[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
      cin >> s;
      Add(s);
    }
    for (int i = 1; i <= t; i++) {
      ans = 0;
      cin >> s;
      cout << check(s) << '\n';
    }
  }
  return 0;
}

样例没错,脚造数据也没错


by WaterSun @ 2023-01-10 14:43:08

@jiangyuchen12 cnt 没有初始化。


by __JiCanDuck__ @ 2023-01-10 14:48:55

@SYC0226 谢谢,但是现在好像评测不出来。之前有3个点是T的


by __JiCanDuck__ @ 2023-01-10 15:01:51

@SYC0226 加上之后还是20全是WA的


by WaterSun @ 2023-01-10 15:05:34

@jiangyuchen12 你的 a 数组是否开小了,第二维应该开个 80 即可。


by WaterSun @ 2023-01-10 15:06:36

@jiangyuchen12 而且你的数字是怎么判断的呢?


by WaterSun @ 2023-01-10 15:07:07

@jiangyuchen12 你的 zhuan 函数应该还要判断一个数字的情况。


by __JiCanDuck__ @ 2023-01-10 15:21:10

@SYC0226 谢谢,刚刚死机了


by __JiCanDuck__ @ 2023-01-10 15:24:35

AC了


|