UVa 11486 Hyper Prefix Sets 字典樹裸題

題意：

給定n個串，找一個字符串u，設前綴為u的字符有v個，則權值為 u*v，求最大的權值

思路：把所有串插到字典樹中，答案就是節點深度*該節點的覆蓋數

#include 
#include 
#include 
#include 
#include 
#include 
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;
		queueq; 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;
}