思路:kmp+子串枚举
分析:
1 题目要求的是给定m个DNA序列,每个DNA序列长度固定为60,问m个DNA序列的最长的公共子串
2 初看题目无从下手,但是你仔细研究发现是要找m个序列的公共子串,那么这个子串必定存在于第一个DNA序列里面。这个时候就可以想到去枚举第一个DNA序列的所有子串,由于长度为60那么最多3600个子串,由于m最多10个;所以算一下复杂度就是0(3600*n*m),n是60和m最大10,那么这样的复杂度是可以接受的。
代码:
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> using namespace std; #define MAXN 70 #define N 11 int t , m; char DNA[N][MAXN]; int next[MAXN]; /*求next数组*/ void getNext(char *str){ int len = strlen(str); next[0] = next[1] = 0; for(int i = 1 ; i < len ; i++){/*这里从1开始*/ int j = next[i]; while(j && str[i] != str[j]) j = next[j]; next[i+1] = str[i] == str[j] ? j+1 : 0; } } /*查找*/ bool find(char *str , char *tmpDNA){ int len = strlen(str); int j = 0; for(int i = 0 ; i < 60 ; i++){ while(j && str[j] != tmpDNA[i]) j = next[j]; if(str[j] == tmpDNA[i]) j++; if(j == len)/*如果找到了return true*/ return true; } return false; } int main(){ int maxLen , vis; char ans[MAXN]; char tmp[MAXN]; scanf("%d" , &t); while(t--){ scanf("%d" , &m); for(int i = 0 ; i < m ; i++) scanf("%s" , DNA[i]); /*枚举第一个DNA序列的所有子串*/ maxLen = 0; for(int i = 0 ; i < 60 ; i++){/*枚举起点*/ memset(tmp , '\0' , sizeof(tmp)); int cnt = 0; for(int j = i ; j < 60 ; j++){/*枚举终点*/ tmp[cnt++] = DNA[0][j]; vis = 1; for(int k = 1 ; k < m ; k++){ if(!find(tmp , DNA[k])){/*没找到就是不满足直接break*/ vis = 0; break; } } /*如果tmp是m个序列的共同子序列则判断长度*/ if(vis){ if(maxLen < cnt){ maxLen = cnt; memcpy(ans , tmp , sizeof(tmp)); } /*长度相等则判断字典序*/ else if(maxLen == cnt && strcmp(ans , tmp) > 0) memcpy(ans , tmp , sizeof(tmp)); } } } if(maxLen < 3) printf("no significant commonalities\n"); else printf("%s\n" , ans); } return 0; }