• <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 }
            青青草国产精品久久| 久久综合综合久久97色| 久久国产成人午夜aⅴ影院| 国产综合成人久久大片91| 久久久久久无码国产精品中文字幕 | 久久精品国产99久久丝袜| 国内精品久久久久久久亚洲| 国产成人精品综合久久久| 精品一区二区久久| 性色欲网站人妻丰满中文久久不卡| 精品久久久无码中文字幕天天| 久久精品国产黑森林| 午夜精品久久久久久中宇| 久久91精品综合国产首页| 日本久久久久亚洲中字幕| 伊人久久大香线蕉综合网站| 国产精品免费久久久久久久久| 99久久99这里只有免费的精品| 久久精品免费一区二区| 久久亚洲国产最新网站| 久久成人18免费网站| 国产欧美一区二区久久| 亚洲午夜久久久久久噜噜噜| 成人综合久久精品色婷婷| 亚洲日本va午夜中文字幕久久 | 久久亚洲国产精品五月天婷| 久久久久国产一区二区| 久久精品国产秦先生| 97久久精品无码一区二区| 久久久久久人妻无码| 精品国际久久久久999波多野| 久久国产色AV免费看| 亚洲精品乱码久久久久久久久久久久 | 人妻少妇久久中文字幕| 久久婷婷色综合一区二区| 久久国产欧美日韩精品| 久久精品国产免费观看| 亚洲国产精品无码久久久蜜芽| 亚洲乱码日产精品a级毛片久久| 亚洲午夜无码久久久久小说| 亚洲午夜精品久久久久久浪潮 |