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

            最小公共子序列

            Longest Common Subsequence

            Problem

            Given a sequence A = < a1, a2, ..., am >, let sequence B = < b1, b2, ..., bk > be a subsequence of A if there exists a strictly increasing sequence ( i1<i2<i3 ..., ik ) of indices of A such that for all j = 1,2,...,k, aij = bj. For example, B = < a, b, c, d > is a subsequence of A= < a, b, c, f, d, c > with index sequence < 1, 2, 3 ,5 >.
            Given two sequences X and Y, you need to find the length of the longest common subsequence of X and Y.

            Input

            The input may contain several test cases.

            The first line of each test case contains two integers N (the length of X) and M(the length of Y), The second line contains the sequence X, the third line contains the sequence Y, X and Y will be composed only from lowercase letters. (1<=N, M<=100)

            Input is terminated by EOF.

            Output

            Output the length of the longest common subsequence of X and Y on a single line for each test case.

            Sample input

            6 4
            abcfdc
            abcd
            2 2
            ab
            cd

            Sample output

            4
            0

            #include <stdio.h>
            char x[105],y[105];
            int c[109][109],i,j,leny,lenx;
            int main(){
                
            while(scanf("%d %d",&lenx,&leny)!=EOF){
                    scanf(
            "%s",&x);
                    scanf(
            "%s",&y);
                    
            for(i=0;i<=leny;i++)
                        c[
            0][i]=0;
                    
            for(i=1;i<=lenx;i++)
                        c[i][
            0]=0;
                    
            for(i=1;i<=lenx;i++){
                        
            for(j=1;j<=leny;j++){
                            
            if(x[i-1]==y[j-1])
                                c[i][j]
            =c[i-1][j-1]+1;
                            
            else{
                                
            if(c[i-1][j]>=c[i][j-1])
                                    c[i][j]
            =c[i-1][j];
                                
            else c[i][j]=c[i][j-1];
                            }

                        }

                    }

                    printf(
            "%d\n",c[lenx][leny]);
                }

                
            return 0;
            }

            posted on 2008-04-08 13:27 zhongguoa 閱讀(484) 評論(0)  編輯 收藏 引用
            国产精品美女久久久免费| 久久国产影院| 久久精品国产亚洲AV大全| 久久r热这里有精品视频| 亚洲成人精品久久| 久久国产视屏| 亚洲国产精品无码久久| 亚洲伊人久久大香线蕉苏妲己| 久久久久无码精品国产app| 精品国产99久久久久久麻豆 | 国产精品成人99久久久久| 热久久国产欧美一区二区精品| 五月丁香综合激情六月久久| 国产精品va久久久久久久| 亚洲国产欧美国产综合久久| 国产精品免费久久久久电影网| 久久热这里只有精品在线观看| 青青青青久久精品国产h| 亚洲精品国精品久久99热一| 久久精品亚洲福利| 18岁日韩内射颜射午夜久久成人 | 久久久久久国产精品无码超碰| 国产精品伦理久久久久久| 国产Av激情久久无码天堂| 久久久久精品国产亚洲AV无码 | 久久精品国产亚洲精品2020| 美女久久久久久| 国产农村妇女毛片精品久久| 久久本道伊人久久| 秋霞久久国产精品电影院| 久久婷婷激情综合色综合俺也去| 久久中文字幕精品| 伊人久久综合精品无码AV专区 | 国产日产久久高清欧美一区| 亚洲伊人久久大香线蕉综合图片| 伊人久久大香线蕉AV一区二区| 久久国产乱子伦精品免费午夜| 国产精品日韩欧美久久综合| 国产福利电影一区二区三区,免费久久久久久久精 | 色综合久久无码中文字幕| 久久综合视频网|