題面
題解
- 我們可以用字典樹來查詢串中是否出現前綴，對于每個字串，我們先判斷其是不是前面字串的前綴，或者前面字串是不是它的前綴，然后再插入即可
- 我們可以將每個字串的結尾標記，那么每次query的時候，如果當前字串在原字典樹中全部出現，那么這個字串就是某個字串的前綴，如果當前字串從根節點開始向下查詢時有一個節點的cnt>0,說明當前這個字串有前綴存在于字典樹中，
代碼
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100010;
int t, n;
char s[10];
int tr[N][10], cnt[N], idx;
void insert(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - '0';
if (!tr[p][u]) tr[p][u] = ++idx;
p = tr[p][u];
}
cnt[p]++;
}
bool query(char str[]) {
int p = 0;
for (int i = 0; str[i]; i++) {
int u = str[i] - '0';
if (!tr[p][u]) return false;
p = tr[p][u];
if (cnt[p] > 0) return true;
}
return true;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cin >> t;
while (t--) {
idx = 0;
memset(cnt, 0, sizeof cnt);
memset(tr, 0, sizeof tr);
cin >> n;
bool flag = true;
while (n--) {
cin >> s;
if (query(s)) flag = false;
insert(s);
}
if (flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/264182.html
標籤：其他
上一篇：Flutter與原生雙向通信BasicMessageChannel(IOS暫未測驗)
下一篇：快讓你的App分20億吧！