UVA 11488
題目鏈接https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2483
給定若干個(gè)01字符串,從這些字符串中選出一個(gè)集合,使得這個(gè)集合所有字符串的最長公共前綴和字符串個(gè)數(shù)相乘最大.
思路:
比較裸的一棵字典樹,回想一下字典樹的性質(zhì),因?yàn)槭窃诓煌墓?jié)點(diǎn)的時(shí)候進(jìn)行分叉,而一個(gè)節(jié)點(diǎn)可能又多個(gè)分叉點(diǎn),如果有3個(gè)分叉點(diǎn)說明到這個(gè)節(jié)點(diǎn)的長度就是這三個(gè)分叉也就是三個(gè)字符串的最長公共前綴的長度,然后再乘分叉數(shù)和原來的ans比較就可以獲得答案了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxnode = 50010 * 2;
const int sigma_size = 12;
long long ans;
struct Trie{
int ch[maxnode][sigma_size];
int cnt[maxnode];
int sz;
void clear(){
sz = 1;
ans = 0;
memset(ch, 0, sizeof(ch));
memset(cnt, 0, sizeof(cnt));
}
int idx(char c){
return c - '0';
}
void insert(char *s){
int u = 0, n = strlen(s);
for(int i = 0;i < n;i ++){
int c = idx(s[i]);
if (!ch[u][c]){
memset(ch[sz], 0, sizeof(ch[sz]));
ch[u][c] = sz ++;
}
u = ch[u][c];
cnt[u] ++;
ans = max(ans,(long long)cnt[u] * (i + 1));
}
}
};
Trie trie;
int n, t;
char ss[maxnode];
int main(){
scanf("%d", &t);
while (t --){
trie.clear();
scanf("%d", &n);
for (int i = 0;i < n;i ++){
scanf("%s", ss);
trie.insert(ss);
}
cout << ans << endl;
}
return 0;
}
