• <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個(gè)字符串的shortest common superstring,最小公共父串:使得str1和str2都包含在所求的superstring中,且該superstring的長度最小。設(shè)str1的長度為m,str2的長度為n,如果按照逐個(gè)位置匹配求公共部分的方法,時(shí)間復(fù)雜度為O(m*n)。題目中的n∈[1,1000000],顯然會(huì)TLE,必須降低時(shí)間復(fù)雜度,只能用KMP模式匹配算法來做了,時(shí)間復(fù)雜度O(m+n)。
               用KMP算法來求解時(shí),分3種情況:
               ----str1與str2能完全匹配,長度為max{len1,len2},如banana,ban;
               ----str1與str2不能匹配,但是能找到公共部分,如字符串a(chǎn)lba,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 極限定律 閱讀(619) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

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

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            日本精品一区二区久久久| 一本一道久久精品综合| 亚洲日本va中文字幕久久| 亚洲狠狠婷婷综合久久蜜芽| 久久er国产精品免费观看2| 久久男人中文字幕资源站| 久久综合给合久久狠狠狠97色69 | 精品国产乱码久久久久久人妻| 久久这里只精品99re66| 91精品国产综合久久婷婷| 久久久精品国产Sm最大网站| 久久精品国产亚洲av高清漫画| 狠狠综合久久综合中文88| 国产精品女同久久久久电影院| 久久国产精品国语对白| 97久久精品无码一区二区天美| 久久精品无码一区二区三区日韩| 久久国产色AV免费观看| 人妻无码αv中文字幕久久琪琪布| 99久久精品免费| 99久久er这里只有精品18| 久久无码中文字幕东京热| 色欲综合久久躁天天躁| 国产日韩久久久精品影院首页| 九九精品99久久久香蕉| 久久婷婷五月综合国产尤物app| 久久精品中文字幕一区| 7国产欧美日韩综合天堂中文久久久久| 国产成人精品综合久久久久| 亚洲精品视频久久久| 欧美日韩成人精品久久久免费看| 一本一道久久精品综合| 国产精品永久久久久久久久久| 91精品国产综合久久久久久| 久久精品国产亚洲AV电影| 国产Av激情久久无码天堂| 波多野结衣中文字幕久久 | 91精品国产综合久久香蕉| 久久99国产精品久久| 999久久久免费国产精品播放| 蜜桃麻豆www久久|