poj3080（Blue Jeans）

题目地址：Blue Jeans

题目大意：

人的DNA都是由碱基序列构成的（G,A,T,C），给你m个DNA序列每行都是由60哥字符构成，找出这m行里最长的公共子序列，如果长度小于三输出“no significant commonalities”。否则输出最长的公共子序列。

解题思路：

因为数据很小，暴力即可。先将第一个字符串做为母串，将母串分割长度为len=（1.2.3....60）的字符串存到数组里，然后枚举len=1时母串的所有可能性，分别向下面的字符串比较，如果下面的字符串都包含你所分割的长度的字符串，然后记录此分割的字符串。依次枚举len=2...len=60，因为还要按字典序输出，所以你存找到的公共子序列时遇见下一个同样长度的公共子序列，需要比较一下。

代码：

  1 #include <algorithm>
  2 #include <iostream>
  3 #include <sstream>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cstdio>
  7 #include <string>
  8 #include <bitset>
  9 #include <vector>
 10 #include <queue>
 11 #include <stack>
 12 #include <cmath>
 13 #include <list>
 14 //#include <map>
 15 #include <set>
 16 using namespace std;
 17 /***************************************/
 18 #define ll long long
 19 #define int64 __int64
 20 /***************************************/
 21 const int INF = 0x7f7f7f7f;
 22 const double eps = 1e-8;
 23 const double PIE=acos(-1.0);
 24 const int d1x[]= {-1,1,0,0};
 25 const int d1y[]= {0,0,-1,1};
 26 const int d2x[]= {0,-1,0,1};
 27 const int d2y[]= {1,0,-1,0};
 28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
 29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
 30 /***************************************/
 31 void openfile()
 32 {
 33     freopen("data.in","rb",stdin);
 34     freopen("data.out","wb",stdout);
 35 }
 36 /**********************华丽丽的分割线,以上为模板部分*****************/
 37 char s[20][65];
 38 char c[65][65];
 39 char dna[65];
 40 int main()
 41 {
 42     int n;
 43     scanf("%d",&n);
 44     while(n--)
 45     {
 46         memset(s,0,sizeof(s));
 47         memset(c,0,sizeof(c));
 48         memset(dna,0,sizeof(dna));
 49         int m;
 50         int  i,j,k,h;
 51         scanf("%d",&m);
 52         for(i=0; i<m; i++)
 53             scanf("%s",s[i]);
 54         int len=1;
 55         while(1)
 56         {
 57             int d1=0,d2=0;
 58             for(j=0; j<60; j++)
 59             {
 60                 for(i=0; i<len; i++)
 61                     c[d1][i]=s[0][j+i];
 62                 d1++;
 63                 if (60-j==len)
 64                     break;
 65             }
 66             int cnt1,cnt2,cnt3;
 67             for(cnt3=0,j=0; j<d1; j++)
 68             {
 69                 for(cnt2=0,i=1; i<m; i++)
 70                 {
 71                     for(h=0; h<60; h++)
 72                     {
 73                         for(cnt1=0,k=0; k<len; k++)
 74                         {
 75                             if (c[j][k]==s[i][h+k])
 76                                 cnt1++;
 77                         }
 78                         if (cnt1==len)
 79                         {
 80                             cnt2++;
 81                             break;
 82                         }
 83                     }
 84                 }
 85                 if (cnt2==m-1)
 86                 {
 87                     if (!cnt3)
 88                         strcpy(dna,c[j]);
 89                     else
 90                     {
 91                         for(i=0;i<len;i++)
 92                         {
 93                             if (c[j][i]>dna[i])
 94                                 break;
 95                             if (c[j][i]<dna[i])
 96                                 strcpy(dna,c[j]);
 97                         }
 98                     }
 99                     cnt3++;
100                 }
101             }
102             len++;
103             if (len==61)
104                 break;
105         }
106         int ce=strlen(dna);
107         if (ce<3)
108             printf("no significant commonalities\n");
109         if (ce>=3)
110             printf("%s\n",dna);
111     }
112     return 0;
113 }
114 /*TTTTTTTTTTTTTTTTTTTTTTTTTAGATACTTTTTTTTTTTTTTTTTTTTTTTTTTTTT */

View Code

poj3080（Blue Jeans）

推荐阅读