菜单

最长前缀生物学

2019年3月27日 - 生物学

标题叙述

在生物学中,一些海洋生物的构造是用饱含其要素的大写字母体系来代表的。生物学家对于把长的队列分解成较短的系列(即成分)很感兴趣。

假定二个集合 P 中的成分得以由此串联(成分得以重复使用,也就是 Pascal中的 “+” 运算符)组成一个类别 S ,那么咱们觉得连串 S 能够解释为 P
中的成分。成分不自然要一五一十并发(如下例中BBC就从不出现)。举个例子,种类ABABACABAAB 能够解释为上面集合中的成分:

{A, AB, BA, CA, BBC}

队列 S 的方今 K 个字符称作 S 中长度为 K
的前缀。设计一个先后,输入一个因素集合以及一个大写字母种类 S
,设S’是体系S的最长前缀,使其能够表达为付出的集合P中的元素,求S’的长度K。

输入输出格式

输入格式:

 

输入数据的起先包涵 1..200 个要素(长度为 1..10
)组成的联谊,用再而三的以空格分开的字符串表示。字母全体是大写,数据大概不止一行。成分集合实现的申明是多个只包罗一个“.” 的行。集合中的成分没有重新。接着是大写字母体系 S ,长度为 1..200,000
,用一行只怕多行的字符串来代表,每行不超越 76 个字符。换行符并不是种类 S
的一某些。

 

出口格式:

 

唯有一行,输出叁个整数,表示 S 符合条件的前缀的最大尺寸。

 

输入输出样例

输入样例#1:

A AB BA CA BBC
.
ABABACABAABC

出口样例#1:

11

说明

翻译来自NOCOW

生物学,USACO 2.3

 

【分析】

map大法好,本来觉得会慢,结果还足以。

然后就是dp的思考啦,能达到规定的标准的点都标志为true,最终从后往前找最大的点。

 

【代码】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 map<string, bool> Map;
 5 string s, str;
 6 bool dp[200025];
 7 int len;
 8 
 9 void init() {
10     while (cin >> s && s!=".")
11         Map[s]=true;
12     str=" ";
13     while (cin >> s)
14         str+=s;
15     len=str.length()-1;
16     dp[0]=true;    
17 } 
18 
19 void DP() {
20     for (int i=1;i<=len;++i)
21         for (int j=1;j<=min(i, 10);++j) 
22             if (dp[i-j] && Map[str.substr(i-j+1, j)]) {
23                 dp[i]=true;
24                 break;
25             }
26     for (int i=len;i>=0;--i)
27         if (dp[i]) {
28             cout << i << endl;
29             return;    
30         }
31 }
32 
33 int main() {
34     init();
35     DP();
36 }

 

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图