本文共 1177 字，大约阅读时间需要 3 分钟。
题意：给定一些字符串，要求两两比較，须要比較的总次数（注意。假设一个字符同样。实际上要还要和'\0'比一次，相当比2次）
思路：建Trie树，每次建树过程中。后继后继结点就是同样结点须要比較两次ans + val * 2。否则就是不同结点ans + val，建完树就计算完了
代码：
#include#include const int N = 1005;const int MAXN = 4000005;int n;char str[N];long long ans;struct Node { char c; int val;} node[MAXN];int first[MAXN], next[MAXN], sz;void init() { ans = 0; sz = 1; first[0] = 0; next[0] = 0; node[0].val = 0;}void insert(char *str) { int u = 0, len = strlen(str); for (int i = 0; i <= len; i++) { bool flag = true; int v, tmp; for (v = first[u]; v; v = next[v]) { if (node[v].c == str[i]) { tmp = v; flag = false; ans += node[v].val * 2; } else ans += node[v].val; } if (flag) { v = sz++; node[v].c = str[i]; node[v].val = 0; first[v] = 0; next[v] = first[u]; first[u] = v; } else v = tmp; u = v; node[u].val++; }}int main() { int cas = 0; while (~scanf("%d", &n) && n) { init(); while (n--) { scanf("%s", str); insert(str); } printf("Case %d: %lld\n", ++cas, ans); } return 0;}
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5404017.html，如需转载请自行联系原作者