题意:求N个字符串两两比较,共比较了多少次?

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std; typedef long long LL;
const int maxnode = * + ; // 字母表为全体小写字母的Trie
struct Trie
{
int head[maxnode]; // head[i]为第i个结点的左儿子编号
int next[maxnode]; // next[i]为第i个结点的右兄弟编号
char ch[maxnode]; // ch[i]为第i个结点上的字符
int tot[maxnode]; // tot[i]为第i个结点为根的子树包含的叶结点总数
int sz; // 结点总数
LL ans; // 答案
void clear() { sz = ; tot[] = head[] = next[] = ; } // 初始时只有一个根结点 // 插入字符串s(包括最后的'\0'),沿途更新tot
void insert(const char *s)
{
int u = , v, n = strlen(s);
tot[]++;
for(int i = ; i <= n; i++)
{
// 找字符a[i]
bool found = false;
for(v = head[u]; v != ; v = next[v])
if(ch[v] == s[i]) { found = true;break;}
if(!found)
{
v = sz++; // 新建结点
tot[v] = ;
ch[v] = s[i];
next[v] = head[u];//v添加右兄弟节点
head[u] = v; // u添加左儿子节点
head[v] = ;
}
u = v;
tot[u]++;
}
} // 统计LCP=u的所有单词两两的比较次数之和
void dfs(int depth, int u)
{
int v;
if(head[u] == ) // 叶结点
ans += tot[u] * (tot[u] - ) * depth;
else
{
int sum = ;
for(v = head[u]; v != ; v = next[v])
sum += tot[v] * (tot[u] - tot[v]); // 子树v中选一个串,其他子树中再选一个
ans += sum / * ( * depth + ); // 除以2是每种选法统计了两次
for(v = head[u]; v != ; v = next[v])
dfs(depth+, v);
}
} // 统计
LL count()
{
ans = ;
dfs(, );
return ans;
}
}; #include<cstdio>
const int maxl = + ; // 每个单词最大长度 int n;
char word[maxl];
Trie trie; int main()
{
int kase = ;
while(scanf("%d", &n) == && n)
{
trie.clear();
for(int i = ; i < n; i++)
{
scanf("%s", word);
trie.insert(word);
}
printf("Case %d: %lld\n", kase++, trie.count());
}
return ;
}

最新文章

  1. daima
  2. MongoDB系列二
  3. background-position
  4. Android本地数据存储复习
  5. SlidesJS - 老牌的响应式 jQuery 幻灯片插件
  6. java-Spring-1
  7. UTF-8 BOM(EF BB BF)
  8. SQL2008-中不想插入从复记录
  9. 【转】搭建Mac OS X下cocos2d-x的Android开发环境
  10. L9-2.安装mysql数据库
  11. Spark之搜狗日志查询实战
  12. ssh禁止密码登录
  13. 学习资料分享(Java第一行代码视频)&lt;susmote.com&gt;
  14. C++中的基础特性:封装,继承,多态
  15. Android WebView 实现网页缩放
  16. K-means &amp;K-medoids 聚类
  17. 【转】web.xml配置项详解
  18. 洛谷P2216 理想的正方形
  19. [Java学习] Java方法重载
  20. WebService学习总结(转)

热门文章

  1. 二叉树、二叉搜索树、平衡二叉树、B树、B+树的精确定义和区别探究
  2. Vue 后台管理
  3. MarkdownPad 2 Pro 注册码
  4. webgis技术在智慧城市综合治理网格化社会管理平台(综治平台)的应用
  5. 01_5_SERVLET为什么有2个init方法
  6. (转发)IOS高级开发~Runtime(三)
  7. 理解JS闭包的几个小实验
  8. bzoj4666 小z的胡话
  9. 【启发式搜索】Codechef March Cook-Off 2018. Maximum Tree Path
  10. vim中,在编辑模式下如何快速移动光标