本文主要是介绍Trie树入门：HDU 1671，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：就是每个串中如果有其他串是它的子串，则输出NO，否则输入YES。
思路：第一点：刚开始……唉……说多了都是泪啊……先前做了1251，然后里面的是s[i]-'a'算的，然后这题是s[i]-'0'，就在这卡了1个半小时，一直RE，郁闷死！！用VS调试了，然后调试竟然对，真是奇了。错的代码，数组下标都是负数了竟然还运行正确……嘛嘛的，让我都不知道哪里错了，搞了好久才知道是算字母时错了。
第二点：就是刚开始还以为是此串前面有子串才是NO，所以在这又错了，如果这个串的后面有它的子串的话，那也是NO， 这点没看清楚题目啊！
第三点：而且子串长度要小于母串，因为打电话到最后一个字的时候即使有串和它一样，也是YES，因为此时已经打通了这个串，不会和其他串重复的……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#define pi acos(-1.0)
#define M 100005
using namespace std;
typedef long long ll;
struct Trie
{int ch[M][11],sz;int val[M],flag;void reset(){sz=1;flag=1;memset(ch,0,sizeof(ch));memset(val,0,sizeof(val));}void insert(char *s){int u=0,i,c,ab=0,l=strlen(s);for(i=0; i<l; i++){c=s[i]-'0'; //在这RE了好多发啊if(!ch[u][c]) {ch[u][c]=sz++;ab=1;} u=ch[u][c];if(val[u]&&i!=l-1) {flag=0;return;} //如果已经存在了子串，并且这个串的这个字符不能是最后一个字符才是}if(!ab) flag=0; //如果进来的这个串，都没有增加一个结点的话，那说明它就是别的串的子串啦val[u]=1; //最后一个字符标记为1，其他为0，为1表明构成一个单词，这是刘妆佳算法经典入门的标准方法}
}T;
int main()
{int t;cin>>t;while(t--){int n;char s[12];T.reset();scanf("%d",&n);getchar();while(n--){scanf("%s",s);if(T.flag) T.insert(s);}if(T.flag) printf("YES\n");else printf("NO\n");}return 0;
}
这篇关于Trie树入门：HDU 1671的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
