• <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 極限定律 閱讀(620) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC

            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲成人精品久久| 久久综合给合久久狠狠狠97色| 国产亚洲美女精品久久久久狼| 青青青伊人色综合久久| 久久99精品国产99久久6| 中文字幕久久久久人妻| 国产精品一久久香蕉国产线看| 久久99精品久久久久久齐齐| 婷婷伊人久久大香线蕉AV | 久久亚洲电影| 久久久久久久久无码精品亚洲日韩 | 四虎影视久久久免费| 久久精品人人槡人妻人人玩AV | 久久综合香蕉国产蜜臀AV| 久久电影网| 久久精品国产半推半就| 一本一本久久aa综合精品| 久久国产精品免费一区| 国产精品毛片久久久久久久| 亚洲成色WWW久久网站| 99久久做夜夜爱天天做精品| 99久久精品免费看国产免费| 久久精品国产亚洲AV无码麻豆| 色狠狠久久综合网| 久久久久久国产精品无码下载| 久久99热精品| 四虎国产永久免费久久| 久久福利青草精品资源站| 99久久精品国产麻豆| 国产亚洲婷婷香蕉久久精品 | 久久精品国产亚洲5555| 伊人久久精品线影院| 久久美女人爽女人爽| 亚洲狠狠久久综合一区77777| 97久久精品无码一区二区| 精品久久久久久无码专区不卡 | 日日狠狠久久偷偷色综合免费 | 91精品国产高清久久久久久io| 久久综合噜噜激激的五月天| 99久久婷婷国产综合亚洲| 国产欧美一区二区久久|