• <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>
            posts - 21, comments - 2, trackbacks - 0, articles - 0

            ZOJ 1170--String Matching

            Posted on 2011-05-12 10:23 acpeng 閱讀(381) 評論(0)  編輯 收藏 引用 所屬分類: ACM程序

            OJ地址: There are lots of techniques for approximate word matching. One is to determine the best substring match, which is the number of common letters when the words are compared letter-byletter.
            The key to this approach is that the words can overlap in any way. For example, consider the words CAPILLARY and MARSUPIAL. One way to compare them is to overlay them:

            CAPILLARY
            MARSUPIAL

            There is only one common letter (A). Better is the following overlay:

            CAPILLARY
                 MARSUPIAL

            with two common letters (A and R), but the best is:

               CAPILLARY
            MARSUPIAL

            Which has three common letters (P, I and L).

            The approximation measure appx(word1, word2) for two words is given by:

                 common letters * 2
            -----------------------------
            length(word1) + length(word2)

            Thus, for this example, appx(CAPILLARY, MARSUPIAL) = 6 / (9 + 9) = 1/3. Obviously, for any word W appx(W, W) = 1, which is a nice property, while words with no common letters have an appx value of 0.
            Input:
            The input for your program will be a series of words, two per line, until the end-of-file flag of -1.
            Using the above technique, you are to calculate appx() for the pair of words on the line and print the result. For example:

            CAR CART
            TURKEY CHICKEN
            MONEY POVERTY
            ROUGH PESKY
            A A
            -1

            The words will all be uppercase.
            Output:
            Print the value for appx() for each pair as a reduced fraction, like this:

            appx(CAR,CART) = 6/7
            appx(TURKEY,CHICKEN) = 4/13
            appx(MONEY,POVERTY) = 1/3
            appx(ROUGH,PESKY) = 0
            appx(A,A) = 1

            Fractions reducing to zero or one should have no denominator

            代碼:

             1 /*
             2 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1170
             3 2011.5.12
             4 */
             5 #include<stdio.h>
             6 #include<string.h>
             7 int main()
             8 {
             9     int i,j,k,lgth1,lgth2,num,max,tmp1,tmp2,flg;
            10     char str1[1000]="\0",str2[1000]="\0";
            11     while(1)
            12     {
            13         scanf("%s",str1);
            14         if(strcmp(str1,"-1")==0)break;
            15         scanf("%s",str2);
            16         num=0; max=0;
            17         lgth1=(int)strlen(str1);
            18         lgth2=(int)strlen(str2);
            19         for(k=0;k<lgth1;k++)
            20         {
            21             j=0;
            22             for(i=k;i<lgth1 && j<lgth2;i++,j++)
            23                 if(str1[i]==str2[j])num++;
            24             if(max<num) max=num;
            25             num=0;
            26         }
            27         num=0;
            28         for(k=0;k<lgth2;k++)
            29         {
            30             j=0;
            31             for(i=k;i<lgth2 && j<lgth1;i++,j++)
            32                 if(str2[i]==str1[j])num++;
            33                     
            34             if(max<num) max=num;
            35             num=0;
            36         }
            37         printf("appx(%s,%s) = ",str1,str2);
            38 
            39         //化簡分式
            40         if(max==0) printf("0\n");
            41         else if(max*2 == lgth1+lgth2) printf("1\n");
            42         else
            43         {
            44             tmp1=max*2;tmp2=lgth1+lgth2;
            45             while(1)
            46             {
            47                 flg=0;
            48                 for(i=2;i<=tmp1;i++)
            49                 {
            50                     if(tmp1%i==0 && tmp2%i==0)
            51                     {
            52                         tmp1=tmp1/i; tmp2=tmp2/i;
            53                         flg=1;
            54                         break;
            55                     }
            56                 }
            57                 if(flg==0break;
            58             }
            59             printf("%d/%d\n",tmp1,tmp2);
            60         }
            61         memset(str1,0,sizeof(str1));
            62         memset(str2,0,sizeof(str2));
            63     }
            64     return 0;
            65 }
            久久精品亚洲乱码伦伦中文| 怡红院日本一道日本久久 | 99久久精品国产一区二区| 久久久久久国产精品无码下载 | 久久久久综合中文字幕 | 亚洲综合久久综合激情久久| 久久精品国产半推半就| 久久国产免费直播| 久久亚洲AV无码精品色午夜 | 久久不射电影网| 欧美午夜A∨大片久久 | 一本久久综合亚洲鲁鲁五月天| 久久久久香蕉视频| 久久99国产综合精品免费| 久久综合九色综合精品| 亚洲另类欧美综合久久图片区| 久久久久亚洲AV无码专区体验| 国产精品欧美久久久久天天影视 | 99久久婷婷国产一区二区| 精品伊人久久久| 香港aa三级久久三级| 午夜不卡久久精品无码免费| 国产成人无码精品久久久久免费| 亚洲综合精品香蕉久久网| 久久久久香蕉视频| 亚洲国产二区三区久久| 久久人人爽人人爽人人AV| 久久久久久久亚洲精品| 久久青青草原综合伊人| 国内精品久久久人妻中文字幕| 久久久www免费人成精品| 亚洲欧美国产精品专区久久| 91精品国产综合久久香蕉| AV无码久久久久不卡网站下载| 色妞色综合久久夜夜| 伊人久久久AV老熟妇色| 97精品国产97久久久久久免费| 日产精品久久久久久久| 久久精品国产男包| 少妇熟女久久综合网色欲| 久久久久久精品久久久久|