首页 > 代码库 > 【bzoj1174】[Balkan2007]Toponyms Trie树
【bzoj1174】[Balkan2007]Toponyms Trie树
题目描述
给你一个字符集合,你从其中找出一些字符串出来. 希望你找出来的这些字符串的最长公共前缀*字符串的总个数最大化.
输入
第一行给出数字N.N在[2,1000000] 下面N行描述这些字符串,长度不超过20000 。保证输入文件不超过10MB
输出
a single line with an integer representing the maximal level of complexity Lc(T).
样例输入
7
Jora de Sus
Orhei
Jora de Mijloc
Joreni
Jora de Jos
Japca
Orheiul Vechi
样例输出
24
题解
Trie树
很显然建立Trie树，用 每个节点的深度*对应字符串个数 更新答案。
但是本题卡空间，不能使用普通的Trie树存边方式，必须使用邻接表（链式前向星）存边。
所以每次插入时扫一遍，看能否扫到该字符，并决定是否添加新边。
时间复杂度$O(53len)$，卡卡常数可以过。另外数组大小已实测。
#include <cstdio>#include <cstring>#include <algorithm>#define N 5000010using namespace std;int tot = 1 , head[N] , to[N] , next[N] , cnt , si[N];char val[N];void add(int x , int y , char c){ to[++cnt] = y , val[cnt] = c , next[cnt] = head[x] , head[x] = cnt;}int main(){ int n , i , j , k , t , p; char ch; long long ans = 0; scanf("%d" , &n); for(i = 1 ; i <= n ; i ++ ) { ch = getchar(); while(ch == ‘\n‘) ch = getchar(); for(j = t = 1 ; ch != ‘\n‘ ; j ++ , ch = getchar()) { for(p = 0 , k = head[t] ; k ; k = next[k]) { if(val[k] == ch) { p = to[k]; break; } } if(!p) add(t , p = ++tot , ch); t = p , si[t] ++ , ans = max(ans , (long long)j * si[t]); } } printf("%lld\n" , ans); return 0;}
【bzoj1174】[Balkan2007]Toponyms Trie树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。