UVAlive5792 Diccionário Portuñol

发布时间:2016-12-6 18:13:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVAlive5792 Diccionário Portuñol",主要涉及到UVAlive5792 Diccionário Portuñol方面的内容,对于UVAlive5792 Diccionário Portuñol感兴趣的同学可以参考一下。

题目 题意:给出P个字符串,从所有字符串的前缀中任选一个,再给T个字符串,从所有字符串的后缀中任选一个,将其拼起来,能得到多少个不同的字符串。 题解: 考虑什么时候会发生重复出现字符串的情况:若P中有ab,T中有bc,那么a+bc和ab+c,产生了两个abc。 所以将T中所有字符串倒置,建立trie树,就可以知道有多少个不同后缀是以a开头,多少个不同后缀以b开头......,如上例中,以b开头的后缀有1个,以c开头的后缀有1个。 再将P中所有字符串建立trie树,考虑trie树的一条链aaab......,如果以aaa为当前P中选出的前缀,后面可以接以任意非b的字母开头的字符串,否则以aaab开头的字符串会被计算两次,依此方法遍历一遍trie树。要考虑的特殊情况,当trie树中某一条链为abcd,遍历到节点c时,若在T中字符串产生的trie树中,d与根节点相连,即存在后缀"d",不能将"abc"+"d"这种情况舍弃掉。 从上,不难发现,重复的次数=P中以字母i结尾的前缀的个数×T中以字母i开头的后缀的个数,'a'<=i<='z' 代码: #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; #define maxn 100005 int p,s; int trie[2][maxn][26],cnt1,cnt2; char st[maxn]; int num[2][26]; void insert(int k,int &cnt) { int node=0; for (int i=0;st[i];i++) { int tmp=st[i]-'a'; if (!trie[k][node][tmp]) { trie[k][node][tmp]=++cnt,num[k][tmp]++; for (int j=0;j<26;j++) trie[k][cnt][j]=0; if (!node) num[k][tmp]--; } node=trie[k][node][tmp]; } } int main() { //freopen("/home/christinass/code/in.txt","r",stdin); while (scanf("%d%d",&p,&s)!=-1) { if (!p&&!s) break; memset(num,0,sizeof(num)); int root=0; cnt1=cnt2=0; for (int i=0;i<26;i++) trie[0][0][i]=trie[1][0][i]=0; for (int i=1;i<=p;i++) { scanf("%s",st); insert(0,cnt1); } for (int i=1;i<=s;i++) { scanf("%s",st); reverse(st,st+strlen(st)); insert(1,cnt2); } long long ans=(long long)cnt1*cnt2; for (int i=0;i<26;i++) ans-=num[0][i]*num[1][i]; printf("%lld\n",ans); } return 0; }

上一篇:Josephus问题
下一篇:随便记几点

相关文章

相关评论