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

            糯米

            TI DaVinci, gstreamer, ffmpeg
            隨筆 - 167, 文章 - 0, 評論 - 47, 引用 - 0
            數據加載中……

            POJ 1229 Wild Domains 動態規劃

            這題看上去很冷門~
            其實也是的,第一眼看上去想不到好的解法,但是將問題稍稍轉化一下就很好辦了。

            思路:
            兩個pattern匹配的過程,如果沒有通配符,那就是從左到右,逐個逐個的匹配。
            由于存在通配符,a的一個節點有可能匹配b的數個節點,同樣,b的一個節點也有可能匹配a的數個節點。
            這就需要搜索了。但是一開始發現搜索的時候通配符的處理真的很麻煩。感覺就是代碼稍微寫錯一點就會WA。

            于是想簡化一下問題。重新定義三種通配符:
            ONE   匹配一個單詞
            ZERO_ONE  匹配零個或一個單詞
            ANY 可以匹配零個或多個單詞

            這樣:
            * = ONE, ANY
            ? = ONE, ZERO_ONE, ZERO_ONE
            ! = ONE, ONE, ONE, ANY

            這樣做的好處是,避免了考慮通配符匹配的單詞數目。
            規劃的時候處理 ONE, ZERO_ONE, ANY 是很簡單的。
            f[a][b] = { 第一個pattern從a處開始匹配,第二個pattern從b處開始匹配,匹配成功則為1,否則為0 }
            轉移的時候:
            f[a][b] = {
            pattern[1][a]為ANY的時候 = f[a + 1][b] || f[a][b + 1] || f[a + 1][b + 1]
            pattern[1][a] 為ONE的時候 = {
                  pattern[2][b] 為 ONE 的時候 = f[a + 1][b + 1]
                  pattern[2][b] 為 ZERO_ONE 的時候 = f[a][b + 1] || f[a + 1][b + 1]
                  ....
                  }
            .....
            }

            #include <stdio.h>
            #include 
            <string.h>

            struct _in {
                
            char *arr[256], line[256];
                
            int cnt;
            }
             in[2];

            enum _node_type {
                ZERO_ONE, ONE, ANY, STR, END
            }
            ;
            struct _node {
                
            enum _node_type type;
                
            char *str;
            }
             stk[2][512];

            int dp[512][512], tm;

            void input(struct _in *t)
            {
                
            int i;

                scanf(
            "%s", t->line);
                
            for (i = t->cnt = 0; ; i++{
                    t
            ->arr[t->cnt++= &t->line[i];
                    
            while (t->line[i] && t->line[i] != '.')
                        i
            ++;
                    
            if (!t->line[i])
                        
            break;
                    t
            ->line[i] = 0;
                }

            }


            void init(struct _in *t, struct _node *s)
            {
                
            int i;

                
            for (i = 0; i < t->cnt; i++{
                    
            switch (*t->arr[i]) {
                    
            case '*':
                        s
            ->type = ONE; s++;
                        s
            ->type = ANY; s++;
                        
            break;
                    
            case '?':
                        s
            ->type = ONE; s++;
                        s
            ->type = ZERO_ONE; s++;
                        s
            ->type = ZERO_ONE; s++;
                        
            break;
                    
            case '!':
                        s
            ->type = ONE; s++;
                        s
            ->type = ONE; s++;
                        s
            ->type = ONE; s++;
                        s
            ->type = ANY; s++;
                        
            break;
                    
            default:
                        s
            ->type = STR;
                        s
            ->str = t->arr[i];
                        s
            ++;
                        
            break;
                    }

                }

                s
            ->type = END;
            }


            int visited(struct _node *a, struct _node *b)
            {
                
            struct _node *t;

                
            if (a > b) {
                    t 
            = a;
                    a 
            = b;
                    b 
            = t;
                }


                
            return dp[a - stk[0]][b - stk[1]] == tm;
            }


            void set_visited(struct _node *a, struct _node *b)
            {
                
            struct _node *t;

                
            if (a > b) {
                    t 
            = a;
                    a 
            = b;
                    b 
            = t;
                }


                dp[a 
            - stk[0]][b - stk[1]] = tm;
            }


            int match(struct _node *a, struct _node *b)
            {
                
            int r = -1;

                
            if (visited(a, b))
                    
            return 0;

                
            if (a->type == ONE) {
                    
            if (b->type == ONE)
                        r 
            = match(a + 1, b + 1);
                    
            if (b->type == ZERO_ONE)
                        r 
            = match(a, b + 1|| match(a + 1, b + 1);
                    
            if (b->type == ANY) 
                        r 
            = match(a, b + 1|| match(a + 1, b + 1|| match(a + 1, b);
                    
            if (b->type == STR)
                        r 
            = match(a + 1, b + 1);
                    
            if (b->type == END)
                        r 
            = 0;
                }


                
            if (a->type == ZERO_ONE) {
                    
            if (b->type == ZERO_ONE)
                        r 
            = match(a + 1, b) || match(a, b + 1|| match(a + 1, b + 1);
                    
            if (b->type == ANY)
                        r 
            = match(a + 1, b) || match(a, b + 1|| match(a + 1, b + 1);
                    
            if (b->type == STR) 
                        r 
            = match(a + 1, b + 1);
                    
            if (b->type == END)
                        r 
            = match(a + 1, b);
                }


                
            if (a->type == ANY) {
                    
            if (b->type == ANY)
                        r 
            = match(a + 1, b) || match(a, b + 1|| match(a + 1, b + 1);
                    
            if (b->type == STR)
                        r 
            = match(a + 1, b) || match(a, b + 1|| match(a + 1, b + 1);
                    
            if (b->type == END)
                        r 
            = match(a + 1, b);
                }


                
            if (a->type == STR) {
                    
            if (b->type == STR)
                        r 
            = !strcmp(a->str, b->str) ? match(a + 1, b + 1) : 0;
                    
            if (b->type == END)
                        r 
            = 0;
                }


                
            if (a->type == END) {
                    
            if (b->type == END)
                        r 
            = 1;
                }


                
            if (r == -1)
                    r 
            = match(b, a);

                
            if (!r)
                    set_visited(a, b);

                
            return r;
            }


            int main()
            {
                
            int t;

                scanf(
            "%d"&t);
                
            while (t--{
                    input(
            &in[0]);
                    input(
            &in[1]);
                    init(
            &in[0], stk[0]);
                    init(
            &in[1], stk[1]);
                    tm
            ++;
                    printf(
            "%s\n", match(stk[0], stk[1]) ? "YES" : "NO");
                }

                
                
            return 0;
            }


             

            posted on 2010-05-26 08:21 糯米 閱讀(773) 評論(0)  編輯 收藏 引用 所屬分類: POJ

            伊人久久久AV老熟妇色| 久久亚洲日韩精品一区二区三区| 国产精品久久久久久一区二区三区 | 女人高潮久久久叫人喷水| 久久精品国产久精国产思思| 狠狠久久亚洲欧美专区 | 国内精品久久久久久久久| 久久天堂AV综合合色蜜桃网| 94久久国产乱子伦精品免费| 色悠久久久久久久综合网| 久久综合色区| 免费久久人人爽人人爽av| 欧美日韩精品久久久免费观看| 国产午夜福利精品久久2021| 久久亚洲中文字幕精品一区| 国产高潮国产高潮久久久| 99久久久久| 久久99热这里只频精品6| 99精品国产综合久久久久五月天 | 久久国产精品视频| 久久99国产精品久久99| 久久天天躁狠狠躁夜夜av浪潮| 无码人妻精品一区二区三区久久 | 日韩久久久久中文字幕人妻| 久久本道伊人久久| 国产成人久久精品激情| 国产精品成人无码久久久久久| 色综合久久久久综合体桃花网| 亚洲精品无码久久不卡| 久久久精品人妻一区二区三区四| 国产精品成人久久久| a级毛片无码兔费真人久久| 亚洲国产成人精品91久久久 | 国内精品伊人久久久久777| 99麻豆久久久国产精品免费| 亚洲乱码精品久久久久..| 欧美国产精品久久高清| 丁香五月网久久综合| 欧美黑人激情性久久| 久久久久这里只有精品 | 99久久婷婷国产一区二区|