• <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 }
            久久91精品久久91综合| 国产免费福利体检区久久| 色偷偷888欧美精品久久久| 久久天堂AV综合合色蜜桃网| 99久久免费国产精品热| 久久无码精品一区二区三区| 一本色综合网久久| 一本大道加勒比久久综合| 伊人久久久AV老熟妇色| 久久国产亚洲精品麻豆| 日本亚洲色大成网站WWW久久 | 久久综合国产乱子伦精品免费| 国产亚洲婷婷香蕉久久精品| 一个色综合久久| 麻豆精品久久久一区二区| 久久亚洲熟女cc98cm| 欧美久久亚洲精品| 国产精品久久久久久| 久久天天躁夜夜躁狠狠躁2022| 久久99精品国产麻豆不卡| 国产成人久久久精品二区三区| 亚洲国产另类久久久精品黑人| 久久精品国产乱子伦| 国产高潮久久免费观看| 久久国产精品无码HDAV| 99久久99这里只有免费费精品| 性做久久久久久久| 亚洲午夜精品久久久久久浪潮| 久久综合日本熟妇| 品成人欧美大片久久国产欧美| 国产高潮国产高潮久久久| 精品一二三区久久aaa片| 久久亚洲AV成人无码软件| 人人狠狠综合88综合久久| 国内精品久久久久久久涩爱| 国产日韩久久久精品影院首页 | 国产精品va久久久久久久| 久久91综合国产91久久精品| 国产精品久久网| 久久久久久综合一区中文字幕| 亚洲国产精品久久|