Trie 模板 WA1~5 AC 6 20 分求助!

P8306 【模板】字典树

Texas_the_Omertosa @ 2023-05-05 21:49:13

RT

//by olkieler
#include <bits/stdc++.h>
#define linf LLONG_MAX
#define iinf INT_MAX
#define ios ios::sync_with_stdio(0);cin.tie(0);
#define N 3000005
#define M 105
#define mod 1000000007
#define pint pair<int, int>
#define mp make_pair
#define fi first
#define se second;
using namespace std;
inline int r(){int x;cin >> x;return x;}
inline void w(int x){cout << x << '\n';}
inline void W(int x){cout << x << ' ';}
int tot;
int rk[125];
int num[N][65];
int ans[N];
inline void insert(string st)
{
  int now = 0;
  for (int i = 0; i < st.size(); i ++)
    {
      if (!num[now][rk[st[i]]])
        {
          num[now][rk[st[i]]] = ++ tot;
        }
      now = num[now][rk[st[i]]];
      ans[now] ++;
    }
}
inline int query(string st)
{
  int now = 0;
  for (int i = 0; i < st.size(); i ++)
    {
      now = num[now][rk[st[i]]];
    }
  return ans[now];
}
int main()
{
  ios;
  //  freopen("P8306_1.in", "r", stdin);
  //  freopen("my.out", "w", stdout);
  int t = r();
  for (int i = 0; i < 26; i ++)
    {
      rk['a' + i] = i + 1;
      rk['A' + i] = i + 27;
    }
  for (int i = 0; i <= 9; i ++)
    {
      rk['0' + i] = i + 53;
    }
  for (int asdf = 1; asdf <= t; asdf ++)
    {
      for (int i = 0; i <= tot; i ++)
        {
          ans[i] = 0;
          for (int j = 0; j < 65; j ++)
            {
              num[i][j] = 0;
            }
        }
      tot = 0;
      int n = r(), q = r();
      for (int i = 1; i <= n; i ++)
        {
          string st;
          cin >> st;
          insert(st);
        }
      for (int i = 1; i <= q; i ++)
        {
          string st;
          cin >> st;
          w(query(st));
        }
    }
  return 0;
}

by SpeedStar @ 2023-05-06 12:48:09

@olkieler 在查询里,如果 st[i] 不是 now 的儿子直接返回 0


by Texas_the_Omertosa @ 2023-05-06 12:51:45

@寒烟冷浅暮殇 已过,thx,但是为什么加上了这个就是对的?


by SpeedStar @ 2023-05-06 13:05:00

@olkieler 因为 t 是前缀


by Texas_the_Omertosa @ 2023-05-06 21:13:49

@寒烟冷浅暮殇 为什么我前缀都没有赋值后缀就会有赋值?


by Acerkaio @ 2023-09-27 19:41:50

@olkieler 你给人家整无语了


by Texas_the_Omertosa @ 2023-09-27 21:02:58

@Acerakoi 有没有一种可能是你太弱了?


by Acerkaio @ 2023-09-28 12:32:20

@olkieler 有没有一种可能人家指是 2 楼的大佬。你看看你写的什么,匹配不下去就从 根 开始继续匹配是吧,你是网络喷子当多了吧。

先好好审视自己再评价他人吧。。


|