• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            poj3080

            Blue Jeans
            Time Limit: 1000MS
            Memory Limit: 65536K
            Total Submissions: 8079
            Accepted: 3376

            Description

            The Genographic Project is a research partnership between IBM and The National Geographic Society that is analyzing DNA from hundreds of thousands of contributors to map how the Earth was populated.

            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

            Input to this problem will begin with a line containing a single integer n indicating the number of datasets. Each dataset consists of the following components:
            • 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

            For each dataset in the input, output the longest base subsequence common to all of the given base sequences. If the longest common subsequence is less than three bases in length, display the string "no significant commonalities" instead. If multiple subsequences of the same longest length exist, output only the subsequence that comes first in alphabetical order.

            Sample Input

            3 2 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA 3 GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA 3 CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT

            Sample Output

            no significant commonalities AGATAC CATCATCAT 

            Source

            South Central USA 2006


            暴力 枚舉+kmp驗證

            我現在終于知道一個好模板有多重要了

            我的渣渣kmp,讓我wa過無數次題目了
            void getnext()
            {
                
            long i,j;
                j
            =-1;
                p[
            0]=-1;//zheli -1
                for (i=1;i<=m-1;i++)
                {
                    
            while ((j!=-1)&&(t[j+1]!=t[i])) j=p[j];//zheli -1
                    if (t[j+1]==t[i]) j=j+1;
                    p[i]
            =j;
                }
            }
            void kmp()
            {
                
            int i,j;
                j
            =-1;
                
            for (i=0;i<=n-1;i++)
                {
                    
            while ((j!=-1)&&(t[j+1]!=s[i])) j=p[j];//zheliyeshi
                    if (t[j+1]==s[i]) j++;
                    
            if (j==m-1)
                    {
                        printf(
            "Find at %d !",i-j+2);
                        j
            =p[j];
                    }
                }
            }
            //就因為這個,改到崩潰


            code
            #include <cstdio>
            #include 
            <cstdlib>
            #include 
            <cstring>
            #include 
            <cmath>
            #include 
            <ctime>
            #include 
            <cassert>
            #include 
            <iostream>
            #include 
            <sstream>
            #include 
            <fstream>
            #include 
            <map>
            #include 
            <set>
            #include 
            <vector>
            #include 
            <queue>
            #include 
            <algorithm>
            #include 
            <iomanip>
            using namespace std;
            char str[15][105];
            char strt[100],old[100],ans[100];
            int p[100];
            int len,n,l1;
            void getnext()
            {
                
            int i,j;
                memset(p,
            0,sizeof(p));
                j
            =-1;
                p[
            0]=-1;
                
            for (i=1;i<strlen(strt);i++)
                {
                    
            while ((j!=-1)&&(strt[j+1]!=strt[i])) j=p[j];
                    
            if (strt[j+1]==strt[i]) j=j+1;
                    p[i]
            =j;
                }
            }
            bool kmp(char str1[])
            {
                
            int i,j,len2;
                len2
            =strlen(strt);
                j
            =-1;
                
            for (i=0;i<60;i++)
                {
                    
            while ((j!=-1)&&(strt[j+1]!=str1[i])) j=p[j];
                    
            if (strt[j+1]==str1[i]) j++;
                    
            if (j==len2-1)
                    {
                        
            return 1;
                    }
                }
                
            if (j!=len2-1)return 0;
                
            else return 1;
            }
            bool cmp1(char strx[],char stry[])
            {
                
            int len1;
                len1
            =strlen(strx);
                
            int len2;
                len2
            =strlen(stry);
                
            int lenx=len1<len2?len1:len2;
                
            for(int i=0; i<lenx; i++)
                {
                    
            if (strx[i]>stry[i])
                    {
                        
            return 1;
                    }
                    
            else if(strx[i]<stry[i])
                    {
                        
            return 0;
                    }
                }
                
            if(len1>len2) return 1;
                
            else return 0;
            }
            int main()
            {
                
            int t,i,j,k;
                scanf(
            "%d",&t);
                
            while(t--)
                {
                    scanf(
            "%d",&n);
                    
            for(i=1; i<=n; i++)
                        scanf(
            "%s",str[i]);
                    len
            =60;
                    l1
            =0;
                    memset(ans,
            0,sizeof(ans));
                    memset(strt,
            0,sizeof(strt));
                    
            for(j=3; j<=len; j++)
                        
            for(i=0; i<=len-j; i++)
                        {
                            strcpy(old,strt);
                            
            for(k=i; k<i+j; k++)
                                strt[k
            -i]=str[1][k];
                            strt[k
            -i]='\0';
                           
            // puts(strt);
                           if(strcmp(old,strt)==0)continue;
                            getnext();
                            
            bool flag;
                            flag
            =true;
                            
            for(k=2; k<=n; k++)
                            {
                                
            if(kmp(str[k])==0)
                                {
                                    flag
            =false;
                                    
            break;
                                }
                            }
                            
            if(flag)
                            {
                                
            if(ans[0]==0)
                                    strcpy(ans,strt);
                                
            else
                                {
                                    
            if(strlen(strt)>strlen(ans))
                                    {
                                        
            //puts(ans);
                                        strcpy(ans,strt);
                                    }
                                    
            else if(strlen(strt)==strlen(ans))
                                    {
                                        
            if(cmp1(ans,strt))
                                        {
                                        
            //    puts(ans);
                                            strcpy(ans,strt);
                                        }
                                    }
                                }

                            }
                        }
                    
            if(ans[0]!=0) printf("%s\n",ans);
                    
            else printf("no significant commonalities\n");
                }
                
            return 0;
            }

            posted on 2012-07-23 21:50 jh818012 閱讀(185) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            国产69精品久久久久久人妻精品| 一本大道久久a久久精品综合| 亚洲日本va午夜中文字幕久久| 四虎国产精品成人免费久久| 蜜桃麻豆www久久国产精品| 久久精品国产亚洲Aⅴ蜜臀色欲| 亚洲va久久久久| 91精品国产91久久久久久蜜臀| 久久综合久久性久99毛片| 人妻少妇久久中文字幕| 国产精品一区二区久久精品无码 | 青青国产成人久久91网| 狠狠综合久久综合中文88| 亚洲色婷婷综合久久| 久久精品中文字幕有码| 久久超乳爆乳中文字幕| 日本精品一区二区久久久| 国产精品久久自在自线观看| 污污内射久久一区二区欧美日韩 | 国内精品伊人久久久久| 婷婷久久五月天| 国产午夜电影久久| 久久久久久夜精品精品免费啦| 亚洲国产成人久久综合野外| 日韩精品国产自在久久现线拍 | 伊人久久精品无码二区麻豆| 国产精品免费久久久久影院| 久久婷婷五月综合97色| 香港aa三级久久三级老师2021国产三级精品三级在 | 久久久亚洲欧洲日产国码二区 | 国产成人久久精品一区二区三区 | 色综合久久久久综合99| 国产精品99久久精品爆乳| 久久九九有精品国产23百花影院| 精品国产乱码久久久久久郑州公司| 漂亮人妻被黑人久久精品| 无码国内精品久久人妻蜜桃| 囯产精品久久久久久久久蜜桃| 久久久久亚洲AV成人网人人网站| 麻豆精品久久久久久久99蜜桃| 国产精品99久久久久久宅男小说|