字典树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;
}