HDU 1671 字典树 查找前缀

本文主要是介绍HDU 1671 字典树 查找前缀，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题意： 若干个电话号码 是否存在某个号码是另一个号码的前缀

将每一个号码都加入一颗字典树中
此时如果这个号码是某个号码的前缀或者某个号码是它的前缀
那么 第一种情况下此号码的节点在某个号码的路径上
第二种情况 在这个号码的路径上存在号码节点

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxnode = 100000 + 50;
const int sigma_size = 15;int ch[maxnode][sigma_size];
int value[maxnode];
int get_idx(char x){return x - '0';
}
int sz;void init_Trie(){sz = 0;memset(value,0,sizeof(value));memset(ch[0],-1,sizeof(ch[0]));
}bool Insert(char* num){int n = strlen(num);int cur = 0;for(int i = 0;i < n;++i){int idx = get_idx(num[i]);if(ch[cur][idx] == -1){sz++;memset(ch[sz],-1,sizeof(ch[sz]));ch[cur][idx] = sz;}cur = ch[cur][idx];if(value[cur]){return false;}}value[cur] = 1;for(int i = 0;i < 10;++i){if(ch[cur][i] != -1){return false;}}return true;
}char N[20];
int main(){int T;scanf("%d",&T);while( T-- ){init_Trie();int n;scanf("%d",&n);bool right = true;for(int i = 0;i < n;++i){scanf("%s",N);if(right){right = right & Insert(N);}}printf("%s\n",right ? "YES" : "NO");}return 0;
}

这篇关于HDU 1671 字典树 查找前缀的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---