POJ3080 Blue Jeans —— 暴力枚举 + KMP / strstr()
题目链接:https://vjudge.net/problem/POJ-3080
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 19152 | Accepted: 8524 |
Description
As an IBM researcher, you have been tasked with writing a program that will find commonalities amongst given snippets of DNA that can be correlated with individual survey information to identify new genetic markers.
A DNA base sequence is noted by listing the nitrogen bases in the order in which they are found in the molecule. There are four bases: adenine (A), thymine (T), guanine (G), and cytosine (C). A 6-base DNA sequence could be represented as TAGACC.
Given a set of DNA base sequences, determine the longest series of bases that occurs in all of the sequences.
Input
- A single positive integer m (2 <= m <= 10) indicating the number of base sequences in this dataset.
- m lines each containing a single base sequence consisting of 60 bases.
Output
Sample Input
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Sample Output
no significant commonalities
AGATAC
CATCATCAT
Source
题解:
找出所有字符串的最长公共连续子串。
直接枚举第一个字符串的每个子串,然后通过kmp算法或者strstr()函数,取判断该子串是否存在于每一个字符串。
KMP:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps = 1e-;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; char s[MAXN][MAXN], tmp[MAXN], ans[MAXN];
int Next[MAXN], Len[MAXN]; void get_next(char x[], int m)
{
int i, j;
j = Next[] = -;
i = ;
while(i<m)
{
while(j!=- && x[i]!=x[j]) j = Next[j];
Next[++i] = ++j;
}
} bool kmp(char x[], int m, char y[], int n)
{
int i, j;
get_next(x, m);
i = j = ;
while(i<n)
{
while(j!=- && y[i]!=x[j]) j = Next[j];
i++; j++;
if(j>=m) return true;
}
return false;
} int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i<=n; i++)
scanf("%s", s[i]), Len[i] = strlen(s[i]); bool hav_ans;
for(int len = Len[]; len>=; len--)
{
hav_ans = false;
for(int st = ; st<=Len[]-len; st++)
{
int en = st+len-, cnt = ;
for(int i = st; i<=en; i++)
tmp[cnt++] = s[][i];
tmp[cnt] = ; bool all = true;
for(int i = ; i<=n; i++)
all = all&&kmp(tmp, cnt, s[i], Len[i]); if(all)
{
if(!hav_ans || strcmp(tmp, ans)<)
{
strcpy(ans, tmp);
hav_ans = true;
}
}
}
if(hav_ans) break;
}
if(hav_ans) puts(ans);
else puts("no significant commonalities");
}
}
strstr():
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <sstream>
#include <algorithm>
using namespace std;
typedef long long LL;
const double eps = 1e-;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = +; char s[MAXN][MAXN], tmp[MAXN], ans[MAXN]; int main()
{
int T, n;
scanf("%d", &T);
while(T--)
{
scanf("%d", &n);
for(int i = ; i<=n; i++)
scanf("%s", s[i]); int Len = strlen(s[]);
bool hav_ans;
for(int len = Len; len>=; len--)
{
hav_ans = false;
for(int st = ; st<=Len-len; st++)
{
int en = st+len-, cnt = ;
for(int i = st; i<=en; i++)
tmp[cnt++] = s[][i];
tmp[cnt] = ; bool all = true;
for(int i = ; i<=n; i++)
all = all&&(strstr(s[i], tmp)); if(all)
{
if(!hav_ans || strcmp(tmp, ans)<)
{
strcpy(ans, tmp);
hav_ans = true;
}
}
}
if(hav_ans) break;
}
if(hav_ans) puts(ans);
else puts("no significant commonalities");
}
}
最新文章
- Python之路Day19-Django(二)
- JFinal - Handler 处理流程
- mvc DropDownList默认选项
- 关于 redis、memcache、mongoDB 的对比(转载)
- mysql 统计
- C r and n(组合数)
- (转)浅谈MD5加密算法中的加盐值(SALT)
- TCP/UDP详解
- .NET强制进行即时垃圾回收
- ADO.NET 快速入门(六):读写 XML
- linux进程,作业,守护进程,进程间同步
- 游戏音频技术备忘 (三) 集成Wwise到Unreal Engine
- (转载)Linux查看文件编码格式及文件编码转换
- 浅谈SSH框架
- 15 ActionBar.Tab 以及保存fragment对象 代码案例
- 关于为什么会涉足easyui
- 微信小程序—文件系统
- Element UI 树形表格,TreeGrid或TreeTable实现
- Google Maps瓦片(tile)地图文件下载(1-11层级)
- HTML5触摸事件(touchstart、touchmove和touchend)