题目大意: 就是现在给出至多10^4个字符串每个长度都在1~40之间, 只包含小写字母, 问如果将其中任意一个串的前缀或者是任意一个串的后缀连接起来可以构成一个新词, 那么包括这些词本身在内一共可以形成多少个不同的词 大致思路: 这个题感觉还是挺巧妙地利用了Trie树来计数, 首先我们将所有的n个串插入到一个Trie树中, 然后将所有串倒过来插入到另外一个Trie书中, 那么trie1中的节点数 - 1就是非空的不同的前缀的数量, trie2 中节点数-1就是不同的后缀数量, 设节点数分别为L1, L2, 那么L1…

2015年5月6日 0条评论 8点热度 阅读全文

题目大意: 在C/C++的函数比较的STL中存在这样的字符串比较函数: int strcmp(char *s, char *t) { int i; for (i=0; s[i]==t[i]; i++) if (s[i]=='\0') return 0; return s[i] - t[i]; } 现在有N个给出的字符串(N <= 1000)且每个字符串长度不超过1000, 现在将这N个字符串两两使用上面的这个函数比较, 问字符比较次数是多少 大致思路: 首先很明显可以用Trie数来统计, 一次插入N个字符串,…

2015年2月12日 0条评论 2点热度 阅读全文

题目大意: 白书例题 给出由S个不同单词组成的字典和一个长字符串. 把这个字符串分解成若干个单词的连接, 单词可以重复使用, 问有多少种分解方法 单词个数1 <= S <=4000, 每个单词长度不超过100, 给出的长字符串长度不超过300000 大致思路: 首先将S个单词插入Trie树, 然后利用递推的思想记忆化搜索即可 代码如下: Result  :  Accepted     Memory  :  ? KB     …

2015年2月11日 0条评论 2点热度 阅读全文