2686 - 最长前缀
时间限制 : 1 秒
内存限制 : 128 MB
在生物学中，一些生物的结构是用包含其要素的大写字母序列来表示的。生物学家对于把长的序列分解成较短的序列（即元素）很感兴趣。
如果一个集合 P 中的元素可以通过串联（元素可以重复使用，相当于 Pascal 中的 “+” 运算符）组成一个序列 S ，那么我们认为序列 S 可以分解为 P 中的元素。元素不一定要全部出现（如下例中BBC就没有出现）。举个例子，序列 ABABACABAAB 可以分解为下面集合中的元素：
{A, AB, BA, CA, BBC}
如果序列S前面K个字符可以由某一集合中的元素组成，那么我们就说这K个字符为序列S的一个长度为K的前缀。设计一个程序，输入一个元素集合以及一个大写字母序列 S ，设S'是序列S的最长前缀，使其可以分解为给出的集合P中的元素，求S'的长度K。
题目输入
输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合，用连续的以空格分开的字符串表示。字母全部是大写，数据可能不止一行。元素集合结束的标志是一个只包含一个 “.” 的行。集合中的元素没有重复。接着是大写字母序列 S ，长度为 1..200,000 ，用一行或者多行的字符串来表示，每行不超过 76 个字符。换行符并不是序列 S 的一部分。
题目输出
只有一行，输出一个整数，表示 S 符合条件的前缀的最大长度。
输入/输出样例
输入格式
A AB BA CA BBC . ABABACABAABC
输出格式
11
C语言解答
#include "stdio.h" #include "string.h" int m,n; char s[200000]; char a[201][11]; int d[201]; int f[200001]; void F(int x,int y) { int i; if(x+d[y]>m) return; for(i=0;i<d[y];i++) if(s[x+i]!=a[y][i]) return; f[x+d[y]]=1; } int main() { int i,j; char c; scanf("%s",a[0]); d[0]=strlen(a[0]); n=0; while(a[n][0]!='.') { n++; scanf("%s",a[n]); d[n]=strlen(a[n]); } m=0; while(~scanf("%c",&c)) { if(c>='A'&&c<='Z') { s[m]=c; m++; } } s[m]=0; f[0]=1; for(i=0;i<m;i++) { if(f[i]) for(j=0;j<n;j++) F(i,j); } for(i=m;i>=0;i--) { if(f[i]) { printf("%d\n",i); break; } } return 0; }
C++解答
/* PROB: prefix LANG: C++ */ #include <fstream> #include<iostream> using namespace std; int main() { //ifstream fin("prefix.in"); //ofstream fout("prefix.out"); string prim[201],str="",t; bool able[200001]={false}; able[0]=true; int i,j,u,v,num=0; while(cin>>t&&t!=".") prim[num++]=t; while(cin>>t) str+=t; for(i=1;i<=str.size();i++) { for(j=0;j<num;j++) { if(prim[j].size()>i) continue; for(u=i-1,v=prim[j].size()-1;v>=0&&str[u]==prim[j][v];u--,v--); if(v<0&&able[i-prim[j].size()]) able[i]=true; } } for(i=str.size();!able[i];i--); cout<<i<<endl; return 0; }