首页 > 代码库 > 【SPOJ】MGLAR10 - Growing Strings
【SPOJ】MGLAR10 - Growing Strings
Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as
it is usually the case in regular farms, they grow strings. A string is a sequence of characters.
Strings have the particularity that, as they grow, they add characters to the left and/or to the
right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at di?erent times during their growth.
The problem is that the collection is not annotated, so they forgot to which string each photo
belongs to. They want to put together a wall to illustrate strings growing procedures, but they
need your help to ?nd an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes imme-
diately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si
appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures,
so all strings in the sequence must be di?erent.
Given a set of strings representing all available photos, your job is to calculate the size of the
largest sequence they can produce following the guidelines above.
Gene and Gina have a particular kind of farm. Instead of growing animals and vegetables, as it is usually the case in regular farms, they grow strings. A string is a sequence of characters. Strings have the particularity that, as they grow, they add characters to the left and/or to the right of themselves, but they never lose characters, nor insert new characters in the middle.
Gene and Gina have a collection of photos of some strings at di?erent times during their growth. The problem is that the collection is not annotated, so they forgot to which string each photo belongs to. They want to put together a wall to illustrate strings growing procedures, but they need your help to ?nd an appropriate sequence of photos.
Each photo illustrates a string. The sequence of photos must be such that if si comes immediately before si+1 in the sequence, then si+1 is a string that may have grown from si (i.e., si appears as a consecutive substring of si+1). Also, they do not want to use repeated pictures, so all strings in the sequence must be di?erent.
Given a set of strings representing all available photos, your job is to calculate the size of the largest sequence they can produce following the guidelines above.
--by spoj
大意是有些字符串，从中选一些收尾相接，要求是相邻两串中前串为后串的子串
求最多用多少串
统计以串x为最长串（总母串）的最大方案，再枚举x取max
统计的方法是：
在标记fail指针时，
若x上有is_end标记，则把fail（x）与fa（x）的方案取max再+1作为x的方案；
若x上无is_end标记，虽然理论上不该有方案，但为了递推方便还是把fail（x）与fa（x）的方案取max（不+1）作为方案，不影响结果
代码：
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char s[1000010];struct Trie{ int ch[26];}data[1000010];int tot;int is_end[1000010],fail[1000010];int que[10000000];void work(int );void Init();void buildfail();int main(){ int n; while(scanf("%d",&n)&&n) work(n); return 0;}void work(int n){ int i,j,k,len,ans=0; Init(); for(i=1;i<=n;i++){ scanf("%s",s); len=strlen(s);k=0; for(j=0;j<len;j++){ if(!data[k].ch[s[j]-‘a‘]) data[k].ch[s[j]-‘a‘]=++tot; k=data[k].ch[s[j]-‘a‘]; } is_end[k]=1; } buildfail(); for(i=0;i<=tot;i++) if(ans<is_end[i]) ans=is_end[i]; printf("%d\n",ans);}void Init(){ memset(fail,0,sizeof(fail)); memset(is_end,0,sizeof(is_end)); memset(data,0,sizeof(data)); tot=0;}void buildfail(){ int h=0,t=1,i,j,k; while(h<t){ h++; for(i=0;i<26;i++) if(data[que[h]].ch[i]){ que[++t]=data[que[h]].ch[i]; j=fail[que[h]]; while(1) if(data[j].ch[i]&&data[j].ch[i]!=que[t]){ fail[que[t]]=data[j].ch[i]; is_end[que[t]]+=is_end[que[h]]>is_end[fail[que[t]]]?is_end[que[h]]:is_end[fail[que[t]]]; break; } else{ if(!j)break; j=fail[j]; } if(!fail[que[t]])is_end[que[t]]+=is_end[que[h]]; } }}
又及，第一次用SPOJ，感觉还不错；
【SPOJ】MGLAR10 - Growing Strings
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。