|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <map> #include <list> #include <stack> using namespace std; #define MAXN 500000 struct trieNode{ int next[2]; int count; int dep; } trie[MAXN]; int boundary = 1; int main(){ int casecnt; cin >> casecnt; while (casecnt--) { int n; boundary = 1; memset(trie, 0, sizeof(trie)); cin >> n; for (int i = 1; i <= n; i++) { string toProc; cin >> toProc; int cur = 0; for (int i = 0; i < toProc.size(); i++) { if (trie[cur].next[toProc[i]-'0'] == 0) { //create node; trie[cur].next[toProc[i]-'0'] = boundary++; } cur = trie[cur].next[toProc[i]-'0']; trie[cur].count++; trie[cur].dep = i + 1; } } int res = 0; for (int i = 1; i < boundary; i++) { res = max(trie[i].dep*trie[i].count,res); } cout << res << endl; } return 0; } |
Trie树，静态方式的话（用数组保存节点），可以比较简单的实现遍历，动态方式（new＋指针）还要写搜索。。。
