UVA11732 "strcmp()" Anyone?
题目链接：https://vjudge.net/problem/UVA-11732
知识点： 字典树、儿子兄弟表示法
解题思路：
首先，为每一个字符的末尾添加一个 '$'，因为有一种特殊情况：如果两个字符串（假设长度为 len ）完全相同，则比较次数是 (2 len + 2) ，因为两个字符串末尾的 ' ' 也是相同的。
用字典树维护字符串集。当插入字符串 (S) 中的一个字符时，算出字典树已有的字符串中跟 (S) 直到上一个字符都是相同的字符串数 (last)，以及插入这个字符后仍然跟 (S) 相同的字符串数 (news)，则对答案的贡献即为 ((news imes 2 + last - news)).
AC代码：
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int maxn = 4000004; 6 7 char ch[maxn]; //保存结点字符 8 int son[maxn], bro[maxn]; //son是链表头, bro[u]表示u的下一个兄弟结点 9 int nds; //nds是下一个可以分配的结点 10 int cnt[maxn]; //cnt[x]表示经过结点x的字符串数 11 12 ll add(char *str) { 13 int len = strlen(str); 14 str[len] = '$', str[len + 1] = '