UVa 11486 Hyper Prefix Sets 字典树裸题

题意：

给定n个串，找一个字符串u，设前缀为u的字符有v个，则权值为 u*v，求最大的权值

思路：把所有串插到字典树中，答案就是节点深度*该节点的覆盖数

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
using namespace std;

#define ll int
struct node{
	int pos, len;
	node(ll a=0, ll b=0):pos(a),len(b){}
};

#define Word_Len 505000
#define Sigma_size 95

struct Trie{
	ll ch[Word_Len][Sigma_size];	 //Word_Len是字典树的节点数 若都是小写字母Sigma_size=26
	ll Have_word[Word_Len];		 //这个节点下有几个单词
	ll val[Word_Len];				 // 这个节点附带的信息，初始化为0表示这个节点不存在单词，所以节点带的信息必须!=0
	ll sz ;						 //当前节点数
	ll pre[Word_Len];  
	char he[Word_Len];  
	ll Newnode(){memset(ch[sz], 0, sizeof(ch[sz])); val[sz]=Have_word[sz]=0; return sz++;}
	void init()							 //初始化字典树
	{ sz = 0; Newnode();}//初始化
	ll idx(char c){return c-32;}	 //字符串编号

	void insert(char *s){	 //把v数字加给 s单词最后一个字母
		ll u = 0, len = strlen(s);
		for(ll i = 0; i < len; i++){
			int c = idx(s[i]);
			if(!ch[u][c])		     //节点不存在就新建后附加
			{
				he[sz] = s[i];
				val[sz] = val[u]+1;
				pre[sz] = u;
				ch[u][c] = Newnode();		
			}
			u = ch[u][c];
			Have_word[u]++;	
		}			//现在的u就是这个单词的最后一个位置
	}
	ll find_word(char *s){
		ll u = 0, len = strlen(s);
		for(ll i = 0; i < len; i++){
			ll c = idx(s[i]);
			if(!ch[u][c])return 0;		//节点不存在
			u = ch[u][c];
		}
		return Have_word[u];
	}
	void Have_name(char *s, ll now){  
		ll len = val[now];  
		s[len--] = ‘\0‘;  
		int cc = now;  
		while(cc!=-1)  
		{  
			s[len--] = he[cc];  
			cc = pre[cc];  
		}  
	} 
	ll find_ans(){
		ll ans = 0;
		queue<node>q; q.push(node(0,0));
		while(!q.empty()){
			node u = q.front(); q.pop();
			ans = max(ans, Have_word[u.pos]*u.len);
			for(ll i = 0; i < Sigma_size; i++){
				node v = node(ch[u.pos][i], u.len+1);
				if(v.pos)
					q.push(v);
			}
		}
		return ans;
	}
};
Trie ac;
char s[1000];
int main(){
	ll T, i, j, k, n;;scanf("%lld",&T);
	while(T--){
		ac.init();
		scanf("%lld",&n);
		while(n--){
			scanf("%s",s);
			ac.insert(s);
		}
		printf("%lld\n",ac.find_ans());
	}
	return 0;
}

UVa 11486 Hyper Prefix Sets 字典树裸题,布布扣,bubuko.com

UVa 11486 Hyper Prefix Sets 字典树裸题

原文：http://blog.csdn.net/acmmmm/article/details/22424409