首页 > 代码库 > Hyper Prefix Sets

Hyper Prefix Sets

2024-07-17 13:46:03   217人阅读

uva11488:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2483

题意：给你n个串，对于一个前缀，如果出现k次，就会得到前缀的长度*k，现在让你求长度*k的最大值。

题解：用trie树来搞。把每个串插入到trie中，记录每个子串出现的次数以及长度，trie树很容易实现，然后插完之后，把每个节点遍历一遍，求最大的len*sum，输出即可。

 1 #include<cstring> 2 #include<vector> 3 #include<cstdio> 4 using namespace std; 5 const int maxnode = 4000 * 1000 + 10; 6 const int sigma_size = 26; 7 char word[10002]; 8 int n,m; 9 int sz;10 struct Trie {11   int head[maxnode]; // head[i]为第i个结点的左儿子编号12   int next[maxnode]; // next[i]为第i个结点的右兄弟编号13   char ch[maxnode];  // ch[i]为第i个结点上的字符14   int sum[maxnode];15   int len[maxnode];16   void clear() {17     sz = 1;18     head[0] = next[0] = 0;19     memset(len,0,sizeof(len));20     memset(sum,0,sizeof(sum));21     }22   void insert(const char *s,int form ,int to) {23     int u = 0, v;24     for(int i = form; i <to; i++) {25       bool found = false;26       for(v = head[u]; v != 0; v = next[v])27         if(ch[v] == s[i]) { // 找到了28           found = true;29           break;30         }31       if(!found) {32         v = sz++; // 新建结点33         ch[v] = s[i];34         next[v] = head[u];35         head[u] = v; // 插入到链表的首部36         head[v] = 0;37       }38       u = v;39       sum[u]++;40       len[u]=i+1;41     }42 }43 }trie;44 int cas;45 int main() {46       scanf("%d",&cas);47   while(cas--) {48        trie.clear();49        scanf("%d",&n);50        for(int i=1;i<=n;i++){51         scanf("%s", word);52            m=strlen(word);53          trie.insert(word,0,m);54        }55        int ans=0;56        for(int i=1;i<sz;i++){57           ans=max(ans,trie.len[i]*trie.sum[i]);58        }59       printf("%d\n",ans);60   }61     return 0;62 }
View Code

 


联系
我们