SPOJ Problem Set (classical)7758. Growing StringsProblem code: MGLAR10 |
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.
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 find an appropriate sequence of photos.
Also, they do not want to use repeated pictures, so all strings in the sequence must be different.
Input
Each test case is given using several lines. The first line contains an integer N representing the number of strings in the set (1 ≤ N ≤ 10^4). Each of the following N lines contains a different non-empty string of at most 1000 lowercase
letters of the English alphabet. Within each test case, the sum of the lengths of all strings is at most 10^6.
The last test case is followed by a line containing one zero.
Output
For each test case output a single line with a single integer representing the size of the largest sequence of photos that can be produced.
Sample
input 6 plant ant cant decant deca an 2 supercalifragilisticexpialidocious rag 0 output 4 2
Added by: | ~!(*(@*!@^& |
Date: | 2010-11-05 |
Time limit: | 5s-30s |
Source limit: | 50000B |
Memory limit: | 256MB |
Cluster: | Pyramid (Intel Pentium III 733 MHz) |
Languages: | All |
Resource: | ACM ICPC2010 – Latin American Regional |
题意:给n个不同字符串,找出一个字符串序列满足前一个字符串是后一个字符串的子串。
思路:将n个字符串构成ac机后,我们可以发现对于一个节点p,如果p->cnt!=0,那么以这个字符串为字符串序列结尾的最大个数个数只与其父亲节点p->father的个数和与其失配点p->fail的个数有关,那么转移方程为:dp[p->next[k]->id]=max(dp[p->id],dp[p->next[k]->fail->id])+p->next[k]->cnt;其中dp[i]为到节点i构成的字符串序列含字符串的最大个数,详见代码
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int MAXN=1000000+100; const int N=1000+100; const int sigma_size=26; int n,sz,head,tail; int dp[MAXN]; struct node { int cnt,id; node *next[sigma_size],*fail; }trie[MAXN],*root,*que[MAXN]; struct AC { node *createnode() { for(int k=0;k<sigma_size;k++) trie[sz].next[k]=NULL; trie[sz].fail=NULL; trie[sz].cnt=0; trie[sz].id=sz; return &trie[sz++]; } void init() { sz=0; head=tail=0; root=createnode(); memset(dp,0,sizeof(dp)); } void insert(char *str) { int len=strlen(str); node *p=root; for(int i=0;i<len;i++) { int k=str[i]-'a'; if(p->next[k]==NULL) p->next[k]=createnode(); p=p->next[k]; } p->cnt++; } void get_fail() { que[tail++]=root; while(head<tail) { node *p=que[head++]; for(int k=0;k<sigma_size;k++) { if(p->next[k]) { if(p==root) p->next[k]->fail=root; else p->next[k]->fail=p->fail->next[k]; dp[p->next[k]->id]=max(dp[p->id],dp[p->next[k]->fail->id])+p->next[k]->cnt; que[tail++]=p->next[k]; } else { if(p==root) p->next[k]=root; else p->next[k]=p->fail->next[k]; } } } } }ac; int main() { //freopen("text.txt","r",stdin); while(~scanf("%d",&n) && n) { ac.init(); for(int i=0;i<n;i++) { char str[N]; scanf("%s",str); ac.insert(str); } ac.get_fail(); int ans=0; for(int i=0;i<sz;i++) ans=max(ans,dp[i]); printf("%d\n",ans); } return 0; }