• <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, 評(píng)論 - 47, 引用 - 0
            數(shù)據(jù)加載中……

            POJ 1229 Wild Domains 動(dòng)態(tài)規(guī)劃

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

            思路:
            兩個(gè)pattern匹配的過程,如果沒有通配符,那就是從左到右,逐個(gè)逐個(gè)的匹配。
            由于存在通配符,a的一個(gè)節(jié)點(diǎn)有可能匹配b的數(shù)個(gè)節(jié)點(diǎn),同樣,b的一個(gè)節(jié)點(diǎn)也有可能匹配a的數(shù)個(gè)節(jié)點(diǎn)。
            這就需要搜索了。但是一開始發(fā)現(xiàn)搜索的時(shí)候通配符的處理真的很麻煩。感覺就是代碼稍微寫錯(cuò)一點(diǎn)就會(huì)WA。

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

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

            這樣做的好處是,避免了考慮通配符匹配的單詞數(shù)目。
            規(guī)劃的時(shí)候處理 ONE, ZERO_ONE, ANY 是很簡單的。
            f[a][b] = { 第一個(gè)pattern從a處開始匹配,第二個(gè)pattern從b處開始匹配,匹配成功則為1,否則為0 }
            轉(zhuǎn)移的時(shí)候:
            f[a][b] = {
            pattern[1][a]為ANY的時(shí)候 = f[a + 1][b] || f[a][b + 1] || f[a + 1][b + 1]
            pattern[1][a] 為ONE的時(shí)候 = {
                  pattern[2][b] 為 ONE 的時(shí)候 = f[a + 1][b + 1]
                  pattern[2][b] 為 ZERO_ONE 的時(shí)候 = 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) 評(píng)論(0)  編輯 收藏 引用 所屬分類: POJ

            国产精品国色综合久久| 精品免费tv久久久久久久| 久久国产精品一区| 亚洲国产成人精品女人久久久| 久久久久久精品免费看SSS | 久久久久中文字幕| 久久国产成人| 国产aⅴ激情无码久久| 久久精品国产一区二区三区日韩| 久久久久久久久久免免费精品 | 亚洲人成电影网站久久| 精品国产99久久久久久麻豆| 久久久久中文字幕| 国产美女亚洲精品久久久综合| 久久免费高清视频| 亚洲乱码中文字幕久久孕妇黑人 | 国产成人久久精品激情| 久久精品无码av| 99精品久久精品| 99精品国产综合久久久久五月天| 91久久精品无码一区二区毛片| 日韩精品久久久肉伦网站| 久久久免费观成人影院| 91精品国产91久久| 国产精品久久国产精品99盘| 色欲av伊人久久大香线蕉影院 | 亚洲av伊人久久综合密臀性色| 久久天天躁狠狠躁夜夜2020老熟妇 | 亚洲欧美国产日韩综合久久| 久久亚洲国产精品一区二区| 久久精品无码专区免费青青| 久久一日本道色综合久久| 久久精品免费全国观看国产| 亚洲人AV永久一区二区三区久久| 久久综合久久综合久久| 亚洲国产成人久久精品影视| 97久久天天综合色天天综合色hd| 久久丫精品国产亚洲av不卡| 久久久精品人妻一区二区三区四 | 中文精品久久久久国产网址| 久久精品视频网|