usaco ★Longest Prefix 最长前缀

★Longest Prefix 最长前缀 在生物学中,一些生物的结构是用包含其要素的大写字母序列来表示的.生物学家对于把长的序列 28 分解成较短的（称之为元素的）序列很感兴趣. 如果一个集合 P 中的元素可以通过串联（允许重复；串联,相当于 Pascal 中的 “+” 运算符） 组成一个序列 S ,那么我们认为序列 S 可以分解为 P 中的元素.并不是所有的元素都必须出现. 举个例子,序列 ABABACABAAB 可以分解为下面集合中的元素: {A, AB, BA, CA, BBC} 序列 S 的前面 K 个字符称作 S 中长度为 K 的前缀.设计一个程序,输入一个元素集合以及一个 大写字母序列,计算这个序列最长的前缀的长度. PROGRAM NAME: prefix INPUT FORMAT 输入数据的开头包括 1..200 个元素（长度为 1..10 ）组成的集合,用连续的以空格分开的字符串 表示.字母全部是大写,数据可能不止一行.元素集合结束的标志是一个只包含一个 “.” 的行.集 合中的元素没有重复.接着是大写字母序列 S ,长度为 1..200,000 ,用一行或者多行的字符串来表 示,每行不超过 76 个字符.换行符并不是序列 S 的一部分. SAMPLE INPUT (file prefix.in) A AB BA CA BBC ABABACABAABC OUTPUT FORMAT 只有一行,输出一个整数,表示 S 能够分解成 P 中元素的最长前缀的长度. SAMPLE OUTPUT (file prefix.out)

11

我最怕就是对这种字符串进行处理特别是换行之类的所以这题理所当然放到最后写，。。。。。。然后不会写看了题解。。。。。。。

按顺序找到该点能延伸到最远的那点并把那点标记为true，再每找到true的点就往后延伸，直到找不到了因为我们是按顺序找true点的所以最后一个也就是最远的一个。

/* ID:jinbo wu LANG:C++ TASK:prefix */ #include<bits/stdc++.h> using namespace std; char a[205][15]; string str; char s[100]; bool f[200010]; int main() { freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); int num=0,ans; scanf("%s",a[num]); while(a[num][0]!='.') { num++; scanf("%s",a[num]); } str=""; while(cin>>s) // cin>>s; str+=s; f[0]=true; for(int i=0;i<=str.length();i++) { if(f[i]) { ans=i; for(int j=0;j<num;j++) { int flag=1; for(int k=0;k<strlen(a[j]);k++) if(str[i+k]!=a[j][k]) { flag=0; break; } if(flag) f[i+strlen(a[j])]=true; } } } cout<<ans<<endl; }