• <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>

            HDOJ 1841 Find the Shortest Common Superstring (最小公共父串)

            Problem Description
            The shortest common superstring of 2 strings S1 and S2 is a string S with the minimum number of characters which contains both S1 and S2 as a sequence of consecutive characters. For instance, the shortest common superstring of “alba” and “bacau” is “albacau”.
            Given two strings composed of lowercase English characters, find the length of their shortest common superstring.
             

            Input
            The first line of input contains an integer number T, representing the number of test cases to follow. Each test case consists of 2 lines. The first of these lines contains the string S1 and the second line contains the string S2. Both of these strings contain at least 1 and at most 1.000.000 characters.
             

            Output
            For each of the T test cases, in the order given in the input, print one line containing the length of the shortest common superstring.
             

            Sample Input
            2
            alba
            bacau
            resita
            mures
             

            Sample Output
            7
            8
               題目要求2個字符串的shortest common superstring,最小公共父串:使得str1和str2都包含在所求的superstring中,且該superstring的長度最小。設str1的長度為m,str2的長度為n,如果按照逐個位置匹配求公共部分的方法,時間復雜度為O(m*n)。題目中的n∈[1,1000000],顯然會TLE,必須降低時間復雜度,只能用KMP模式匹配算法來做了,時間復雜度O(m+n)。
               用KMP算法來求解時,分3種情況:
               ----str1與str2能完全匹配,長度為max{len1,len2},如banana,ban;
               ----str1與str2不能匹配,但是能找到公共部分,如字符串alba,bacau,公共部分ba長度為2;
               ----str1與str2不能匹配,且沒有公共部分,如asdf,ghjk。
             1 #include <iostream>
             2 
             3 #define max(a,b) (a>b?a:b)
             4 #define match(a,b) ((a)==(b))
             5 const int MAXN = 1000001;
             6 int fail[MAXN];
             7 char str[2][MAXN];
             8 
             9 int kmp_pat_match(char *str,int ls,int &i,char *pat,int lp,int &j){
            10     fail[0]=-1,i=0,j;
            11     for(j=1;j<lp;j++){
            12         for(i=fail[j-1];i>=0 && !match(pat[i+1],pat[j]);i=fail[i]);
            13         fail[j]=match(pat[i+1],pat[j])?i+1:-1;
            14     }
            15     for(i=j=0;i<ls&&j<lp;i++)
            16         if(match(str[i],pat[j])) j++;
            17         else if(j)
            18             j=fail[j-1]+1,i--;
            19     return j==lp?(i-lp):-1;
            20 }
            21 int main(){
            22     int i,j,t,u,v,len1,len2,pos;
            23     scanf("%d",&t),getchar();
            24     while(t--){
            25         gets(str[0]),gets(str[1]);
            26         len1=strlen(str[0]),len2=strlen(str[1]);
            27         u=0,pos=kmp_pat_match(str[0],len1,i,str[1],len2,j);
            28         if(pos!=-1) u=len2;
            29         else if(i==len1 && j>0 && match(str[0][len1-1],str[1][j-1])) u=j;
            30         v=0,pos=kmp_pat_match(str[1],len2,i,str[0],len1,j);
            31         if(pos!=-1) v=len1;
            32         else if(i==len2 && j>0 && match(str[1][len2-1],str[0][j-1])) v=j;
            33         printf("%d\n",len1+len2-max(u,v));
            34     }
            35     return 0;
            36 }

            posted on 2009-04-28 13:38 極限定律 閱讀(621) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年4月>
            2930311234
            567891011
            12131415161718
            19202122232425
            262728293012
            3456789

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            欧美亚洲国产精品久久| 久久99热精品| 久久99九九国产免费看小说| 久久青青草视频| 精品久久久噜噜噜久久久| 国产成人久久精品二区三区| 久久人人青草97香蕉| 国产精品成人99久久久久 | 91精品国产91热久久久久福利| 久久久久国产成人精品亚洲午夜| 7777精品久久久大香线蕉| 99久久免费国产特黄| 久久国产亚洲精品| 精品多毛少妇人妻AV免费久久 | 久久久免费精品re6| 久久久久无码中| 久久精品国产半推半就| 久久婷婷色香五月综合激情 | 久久精品人人做人人爽97 | 91精品免费久久久久久久久| 无码国内精品久久综合88 | 精品熟女少妇AV免费久久| 91性高湖久久久久| 国产午夜精品理论片久久影视 | 欧美激情精品久久久久久| 青青草原综合久久大伊人精品| 国产A三级久久精品| 亚洲欧洲久久久精品| 久久中文字幕无码专区| 久久99精品久久久久久噜噜| 国产无套内射久久久国产| 99久久免费国产精品| 亚洲国产天堂久久综合网站| 久久se精品一区二区| 色综合久久最新中文字幕| 一级做a爱片久久毛片| 国产精品内射久久久久欢欢| 99久久精品国产毛片| 久久久久久一区国产精品| 色播久久人人爽人人爽人人片aV | 久久精品国产亚洲AV影院|