您的位置:首页 > 财经 > 金融 > 字典树Trie(专项复习)

字典树Trie(专项复习)

2025/3/15 23:34:10 来源:https://blog.csdn.net/sin1810335764/article/details/141873041  浏览:    关键词:字典树Trie(专项复习)

一.P8306 【模板】字典树

 

题目思路:字典树的板子题,熟练写出insert函数(建树),以及query函数(查询)即可.

代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define N 3000005
#define P 131
ll f1[N];
string s;
char ss[N];
ll n, m, num, ans, t, id;
int cnt[N],ch[N][126];
typedef pair<char, ll>pii;
void clear()
{for (int i = 0; i <= id; i++) {cnt[i] = 0;for (int j = 0; j <= 126; j++) {ch[i][j] = 0;}}id = 0;
}
void insert(string s) {int p=0;for (int i = 0; i <= s.size(); i++) {int j = (int)s[i];if (!ch[p][j]) ch[p][j] = ++id;p = ch[p][j];cnt[p]++;}
}
ll find(string s) {int p = 0;for (int i = 0; i < s.size(); i++) {int j = (int)s[i];if (!ch[p][j]) return 0;p = ch[p][j];}return cnt[p];
}
int main()
{cin >> t;while (t--) {clear();cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> s;insert(s);}for (int i = 1; i <= m; i++) {cin >> s;cout << find(s) << endl;}}return 0;
}

二.P1481 魔族密码

 

题目思路:因为是记录最长词链,我们只要在query函数中,使ans+=cnt[p],即将每个节点的单词个数进行累加即可,insert函数不变.

代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define N 3000005
#define P 131
char s[N];
int ch[N][27],cnt[N];
int n, m, k, num, sum;
void insert(char s[])
{int p = 0;for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!ch[p][q]) ch[p][q] = ++num;p = ch[p][q];}cnt[p]++;
}
int query(char s[]) {int p = 0, ans = 0;for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!ch[p][q]) return 0;p = ch[p][q];ans += cnt[p];}return ans;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++) {cin >> s;insert(s);sum = max(query(s), sum);}cout << sum << endl;return 0;
}

三.P2580 于是他错误的点名开始了

 

题目思路:先把所有的人名字存起来,通过insert函数,这样可以建立从名字到数的映射,标记为1,然后扫一遍,如果为1,输出OK,同时将cnt数组++,如果遇到>1,输出REPEAT,如果为0,说明没有,输出WRONG

代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define N 3000005
#define P 131
char s[N];
int ch[N][27],cnt[N];
int n, m, k, num, sum;
void insert(char s[])
{int p = 0;for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!ch[p][q]) ch[p][q] = ++num;p = ch[p][q];}cnt[p]=1;
}
int query(char s[]) {int p = 0, ans = 0;for (int i = 0; s[i]; i++) {int q = s[i] - 'a' + 1;if (!ch[p][q]) return 0;p = ch[p][q];}if (!cnt[p]) return 0;if (cnt[p] == 1) {cnt[p]++;return 1;}return 2;
}
int main()
{cin >> n;memset(cnt, 0, sizeof(cnt));for (int i = 1; i <= n; i++) {cin >> s;insert(s);}cin >> m;for (int i = 1; i <= m; i++) {cin >> s;int k = query(s);if (k == 0)cout << "WRONG" << endl;if (k == 1)cout << "OK" << endl;if (k == 2)cout << "REPEAT" << endl;}return 0;
}

四.P2922 [USACO08DEC] Secret Message G

 

题目思路:和魔族密码这道题有点像,但是我们要维护两个数组,即一个ans数组记录经过该节点的次数,另一个cnt数组记录以该节点结束的次数,在query时,不断累加ans数组的值,最后再sum - cnt[p] + ans[p](因为在最后时应该把以当前结束的次数去掉).

代码实现:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define N 3000005
#define P 131
ll s[N];
ll ch[N][3],cnt[N],ans[N];
int n, m, k, num=1, sum;
void insert(ll s[])
{ll p = 1;for (int i = 1; i <= k; i++) {ll q = s[i];if (!ch[p][q]) ch[p][q] = ++num;p = ch[p][q];ans[p]++;}cnt[p]++;
}
int query(ll s[]) {ll p = 1;sum = 0;for (int i = 1; i <= k; i++) {ll q = s[i];if (!ch[p][q]) return sum;p = ch[p][q];sum += cnt[p];}return sum - cnt[p] + ans[p];
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> k;for (int j = 1; j <= k; j++) cin >> s[j];insert(s);}for (int i = 1; i <= m; i++) {cin >> k;for (int j = 1; j <= k; j++) cin >> s[j];cout << query(s) << endl;}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com