程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> UVA 11488 Hyper Prefix Sets (Trie)

UVA 11488 Hyper Prefix Sets (Trie)

編輯：C++入門知識

UVA 11488 Hyper Prefix Sets (Trie)

Hyper Prefix Sets

Prefix goodness of a set string islength of longest common prefix*number of strings in the set.For example the prefix goodness of theset {000,001,0011} is 6.You are given a set of binarystrings. Find the maximum prefixgoodness among all possible subsets of these binary strings.

Input

First line of the input contains T(≤20)the number of test cases. Each of the test cases start withn(≤50000) the number of strings. Eachof the next n lines contains a string containing only 0 andMaximum length of each of thesestring is 200.

Output

For each test case output the maximumprefix goodness among all possible subsets of n binarystrings.

Sample Input

0000

0001

10101

010

01010010101010101010

11010010101010101010

010101010101000010001010

010101010101000010001000

010101010101000010001010

01010101010100001010010010100101

01010101010100001010011010101010

00001010101010110101

0001010101011010101

00010101010101001

Output for Sample Input

Problem Setter : Abdullah Al Mahmud

Special Thanks : Manzurur Rahman Khan

題意：
給出N個字符串，要求選出若干個，使得選中的字符串的公共前綴長度與選中字符串的個數的乘積最大。
分析：
簡單粗暴的Trie模板題。
對於Tire中的每一個結點添加兩個信息：該結點的深度及該結點杯訪問的次數，最後求出這兩個信息的最大值就行了，邊加入字符串邊維護就行。

/*
 *
 * Author : fcbruce
 *
 * Time : Sat 04 Oct 2014 09:17:50 PM CST
 *
 */
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#define sqr(x) ((x)*(x))
#define LL long long
#define itn int
#define INF 0x3f3f3f3f
#define PI 3.1415926535897932384626
#define eps 1e-10

#ifdef _WIN32
  #define lld %I64d
#else
  #define lld %lld
#endif

#define maxm 2
#define maxn 5000007

using namespace std;

struct Trie
{
  int ch[maxn][maxm];
  int deep[maxn];
  int cnt[maxn][maxm];
  int MAX;
  int sz;

  Trie()
  {
    sz=1;
    deep[0]=0;
    MAX=0;
    memset(cnt[0],0,sizeof cnt[0]);
    memset(ch[0],0,sizeof ch[0]);
  }

  void clear()
  {
    sz=1;
    deep[0]=0;
    MAX=0;
    memset(cnt[0],0,sizeof cnt[0]);
    memset(ch[0],0,sizeof ch[0]);
  }

  int idx(const char ch)
  {
    return ch-'0';
  }

  void insert(const char *s)
  {
    for (int i=0,j=0;s[i]!='';i++)
    {
      int c=idx(s[i]);
      if (ch[j][c]==0)
      {
        memset(ch[sz],0,sizeof ch[sz]);
        memset(cnt[sz],0,sizeof cnt[sz]);
        deep[sz]=i+1;
        ch[j][c]=sz++;
      }
      j=ch[j][c];
      cnt[j][c]++;
      MAX=max(MAX,deep[j]*cnt[j][c]);
    }
  }
}trie;

char str[233];

int main()
{
#ifdef FCBRUCE
  freopen(/home/fcbruce/code/t,r,stdin);
#endif // FCBRUCE

  int T_T;
  scanf(%d,&T_T);
  
  while (T_T--)
  {
    trie.clear();

    int n;
    scanf(%d,&n);
    
    for (int i=0;i