uva 11488

dsqzhaoyue

题目链接：uva 11488 - Hyper Prefix Sets

题目大意：给出若干个由01组成的字符串，求一个前缀串，长度为k，出现在n个字符串中，输出最大的k*n

解题思路：建立字典树，对应在节点上记录次数即可。维护最大值。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10000000;
struct Tire {
int sz;
int ans;
int node[maxn][2];
int val[maxn];
void init();
int idx(char ch);
void insert(char* s);
}tree;
int main () {
int cas, n;
char str[205];
scanf("%d", &cas);
while (cas--) {
tree.init();
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%s", str);
tree.insert(str);
}
printf("%d\n", tree.ans);
}
return 0;
}
void Tire::init() {
sz = 1;
ans = 0;
memset(val, 0, sizeof(val));
memset(node[0], 0, sizeof(node[0]));
}
int Tire::idx(char ch) {
return ch - '0';
}
void Tire::insert(char* s) {
int n = strlen(s), u = 0;
for (int i = 0; i < n; i++) {
int v = idx(s);
if (node[v] == 0) {
memset(node[sz], 0, sizeof(node[sz]));
node[v] = sz++;
}
u = node[v];
val += (i + 1);
ans = max(ans, val);
}
}