首页 > 代码库 > Dictionary Size

Dictionary Size

2024-07-17 14:15:12   220人阅读

uvaLive5913:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3924

题意：给你n个串，然后你可以用串的非空前缀和非空后缀组成新的单词，问形成新的加上原来的一共有多少种不同的串。

题解：很容易想到，先计算出前缀有多少种，后缀有多少种，然后prenum*sufnum即可，但是这样会有重复计算，必须把重复的减去。所以要思考什么情况下会有重复。

例如 ax 和xb来说，a和xb和ax和b，就是重复。所以要统计多少以x结尾的前缀num1和多少以x开头的后缀，然后ans-=num1*num2即可，但是题目要求的是一共多少个串，所以要考虑原来的，对于原来的串来说，只要len>=2,都可以由前缀和后缀组合而来，所以对于这样的串不需要考虑，结果集中已经包含，只要把len==1的数目加上去即可，因为这些串是无法经过组合形成的。

 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[102]; 8 int n,m; 9 long long pre[30],suf[30];10 bool C[30];11 struct Trie {12   int head[maxnode]; // head[i]为第i个结点的左儿子编号13   int next[maxnode]; // next[i]为第i个结点的右兄弟编号14   char ch[maxnode];  // ch[i]为第i个结点上的字符15   int sz; // 结点总数16   void clear() {17     sz = 1;18     head[0] = next[0] = 0;19     }20   void insert(const char *s,int to) {21     int u = 0, v;22     for(int i = 0; i <to; i++) {23       bool found = false;24       for(v = head[u]; v != 0; v = next[v])25         if(ch[v] == s[i]) { // 找到了26           found = true;27           break;28         }29       if(!found) {30         v = sz++; // 新建结点531         ch[v] = s[i];32         if(i!=0)33         pre[s[i]-‘a‘+1]++;34         next[v] = head[u];35         head[u] = v; // 插入到链表的首部36         head[v] = 0;37       }38       u = v;39     }40 }41 void insert2(const char *s,int to) {42     int u = 0, v;43     for(int i = to-1; i>=0; i--) {44       bool found = false;45       for(v = head[u]; v != 0; v = next[v])46         if(ch[v] == s[i]) { // 找到了47           found = true;48           break;49         }50       if(!found) {51         v = sz++; // 新建结点52         ch[v] = s[i];53         if(i!=to-1)54         suf[s[i]-‘a‘+1]++;55         next[v] = head[u];56         head[u] = v; // 插入到链表的首部57         head[v] = 0;58       }59       u = v;60     }61 }62 }trie1,trie2;63 int main() {64   while(~scanf("%d",&n)) {65        trie1.clear();66        trie2.clear();67        memset(pre,0,sizeof(pre));68        memset(suf,0,sizeof(suf));69        memset(C,0,sizeof(C));70       for(int i=1;i<=n;i++){71         scanf("%s", word);72          m=strlen(word);73         trie1.insert(word,m);74         if(m==1)75             C[word[0]-‘a‘+1] = 1;76         trie2.insert2(word,m);77       }78       long long ans=0;79       ans=(long long)(trie1.sz-1)*(trie2.sz-1);80       for(int i=1;i<=26;i++){81             if(C[i]==1)ans++;82          if(suf[i]==0||pre[i]==0)continue;83         ans-=(suf[i]*pre[i]);84       }85       printf("%lld\n",ans);86   }87   return 0;88 }
View Code

 


联系
我们