Hyper Prefix Sets UVA - 11488

题目链接

思路

我们对所有字符串建 \(Trie\) 树，求答案时，直接在插入新的字符串的时候，把答案更新一下就好了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef pair <int,int> PII;
const int N = 50010,S = 210;
int n;
int tr[N * S][2],cnt[N * S],idx;
int ans;
void insert (string s) {
	int p = 0;
	for (int i = 0;i < s.size ();i++) {
		int t = s[i] - '0';
		if (!tr[p][t]) tr[p][t] = ++idx;
		p = tr[p][t];
		cnt[p]++;
		ans = max (ans,(i + 1) * cnt[p]);
	}
}
int main () {
	int T;
	cin >> T;
	while (T--) {
		ans = 0,idx = 0;
		memset (tr,0,sizeof (tr));
		memset (cnt,0,sizeof (cnt));
		cin >> n;
		for (int i = 1;i <= n;i++) {
			string x;
			cin >> x;
			insert (x);
		}
		cout << ans << endl;
	}
    return 0;
}