POJ - 2001 Shortest Prefixes

思路

在字典樹標記字母出現的次數即可
當發現cnt[p] == 1時，說明這個字母前綴只出現過一次，直接返回即可

代碼

#include<iostream> #include<cstring> #include<algorithm>using namespace std;const int N = 1010 * 26; int son[N][26]; int idx; char str[N][26]; int cnt[N];void insert(char str[]) {int p = 0;for (int i = 0; str[i] != '\0'; i ++) {int u = str[i] - 'a';if(!son[p][u])son[p][u] = ++idx;p = son[p][u];cnt[p]++;}}string query(char str[]) {int p = 0;string s = "";for (int i = 0; str[i] != '\0'; i ++) {int u = str[i] - 'a';p = son[p][u];if(cnt[p] == 1){s += str[i];return s;}else {s += str[i];}}return s; }int main() {int n = 0;while(cin >> str[n]) {insert(str[n]);n++;}for (int i = 0; i < n; i ++) {cout << str[i] << ' ' << query(str[i]) << endl;}return 0; }

總結

以上是生活随笔為你收集整理的kuangbin字典树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。