• <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 閱讀(487) 評論(0)  編輯 收藏 引用
            中文字幕无码av激情不卡久久| 无码任你躁久久久久久| 久久精品黄AA片一区二区三区| 一本一本久久A久久综合精品| 老色鬼久久亚洲AV综合| 国产精品久久久久久福利69堂| 99久久精品国产毛片| 亚洲国产成人久久综合一区77| 伊人久久大香线蕉AV色婷婷色| 久久久久久毛片免费播放| 国产日韩久久免费影院| 久久免费视频1| 国产精品美女久久久| 亚洲伊人久久综合中文成人网| 精品无码久久久久国产| 伊人久久大香线蕉精品不卡| 久久精品中文闷骚内射| 国产欧美久久久精品影院| 一级做a爰片久久毛片人呢| 97久久国产综合精品女不卡| 久久福利片| 久久亚洲精品视频| 久久大香香蕉国产| 久久精品国产AV一区二区三区 | 精品一二三区久久aaa片| 91精品无码久久久久久五月天| 久久精品国产亚洲AV无码娇色| 亚洲欧美国产日韩综合久久| 草草久久久无码国产专区| 久久99精品久久久久子伦| 亚洲欧美成人久久综合中文网 | 久久九九久精品国产| 久久96国产精品久久久| 国产精品美女久久久m| 少妇久久久久久久久久| 亚洲欧美日韩中文久久| 久久精品国产免费观看| 亚洲乱码精品久久久久..| 久久香蕉国产线看观看精品yw| 亚洲中文字幕无码久久精品1 | 久久久久久国产精品美女|