题目给了strcmp()的代码，然后问给出n个串两两之间strcmp总共会用到多少次==操作。建立一棵字典树，节点信息存储一个前缀之前出现的次数即可，另外还需要存储的信息是当前节点 是多少个串的结束点（这样就不用把’\n’也加入树了）
坑点的话，自己wa的原因是没有看到他大小写数字都可以有TAT我用我的只考虑了小写字母的Trie送了好几发wa（貌似每次这种题出错都是这样？
[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942
题意给一个字符串和单词字典，问把字符串分割成词典中存在的单词可以有多少种方法（单词可以重复使用）首先是像dp那样考虑，令d(i)为从第i个字符开始到结束的字符串的方案数，然后可以得出d(i)=sum{d(i+len(x))|单词x是S[i,l]的前缀}。然后就是找一个串有多少个单词前缀了。。。字典树搜索即可搞定，就是在Trie中查找S[i,l]，一路查过去把遇到的是单词节点的地方加上那里的d就可以了。
继续阅读“[训练指南][字典树] 使用前缀关系进行递推 字典树加速 LA 3942”