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

            學習心得(code)

            superlong@CoreCoder

              C++博客 :: 首頁 :: 聯系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

            文字可能放在http://blog.csdn.net/superlong100,此處存放代碼

            常用鏈接

            留言簿(4)

            我參與的團隊

            搜索

            •  

            最新隨筆

            最新評論

            • 1.?re: Poj 1279
            • 對于一個凹多邊形用叉積計算面積 后能根據結果的正負來判斷給的點集的時針方向?
            • --bsshanghai
            • 2.?re: Poj 3691
            • 你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?
            • --acmer1183
            • 3.?re: HDU2295[未登錄]
            • 這個是IDA* 也就是迭代加深@ylfdrib
            • --superlong
            • 4.?re: HDU2295
            • 評論內容較長,點擊標題查看
            • --ylfdrib
            • 5.?re: HOJ 11482
            • 呵呵..把代碼發在這里很不錯..以后我也試試...百度的編輯器太爛了....
            • --csuft1

            閱讀排行榜

            評論排行榜

            #include <iostream>
            #include 
            <string.h>

            struct tree
            {
                tree 
            *next[4], *fail;
                
            int state, flag;
            };

            tree sta[
            500];
            int  indexx;

            tree 
            *root, *p;

            int map(char ch)
            {
                
            if(ch == 'A'return 0;    if(ch == 'C'return 1;
                
            if(ch == 'T'return 2if(ch == 'G'return 3;
            }

            inline 
            void newn()
            {
                sta[indexx].fail 
            = NULL;
                sta[indexx].flag 
            = 0;
                sta[indexx].state 
            = indexx;
                
            for(int i = 0; i < 4; i ++) sta[indexx].next[i] = 0;
            }

            void init()
            {
                indexx 
            = 0;
                newn();
                root 
            = &sta[indexx ++];
            }

            void insert(char ch[])
            {
                
            int id, i = 0;
                p 
            = root;
                
            while(ch[i])
                {
                    id 
            = map(ch[i]);
                    
            if(p->next[id] == 0)
                    {
                        newn();
                        p
            ->next[id] = &sta[indexx ++];
                    }
                    p 
            = p->next[id];
                    i 
            ++;
                }
                p
            ->flag = 1;
            }

            tree 
            *que[10001];

            bool search(tree *q)
            {
                
            while(q != root)
                {
                    
            if(q->flag) return true;
                    q 
            = q->fail;
                }
                
            return false;
            }

            void get_fail()
            {
                
            int close = -1, open = 0, i, pass;
                p 
            = root; p->fail = root;
                que[
            0= root;
                
            while(close < open)
                {
                    p 
            = que[++close];
                    tree 
            *= p;
                    pass 
            = 0;
                    
            if(q->flag == 0) pass = search(q);
                    
            if(pass) q->flag = 1;
                    
            for(i = 0; i < 4; i ++)
                    {
                        
            if(p->next[i] == 0)
                        {
                            
            if(p == root) p->next[i] = root;
                            
            else          p->next[i] = p->fail->next[i];
                        }
                        
            else
                        {
                            
            if(p == root) p->next[i]->fail = root;
                            
            else          p->next[i]->fail = p->fail->next[i];
                            que[
            ++open] = p->next[i];
                        }
                    }
                }
            }

            inline 
            void updata(int &a, int b)
            {
            if(a < 0 || b < a) a = b;}

            int f[1005][500];

            int dp()
            {
                
            char str[1005];
                memset(f,
            -1,sizeof(f));
                scanf(
            "%s", str);
                
            int L = strlen(str), inc, dic;
                f[
            0][0= 0;
                
            for(int i = 0; i < L; i ++)
                {
                    
            for(int J = 0; J < indexx; J ++)
                    
            if(f[i][J] >= 0 && sta[J].flag == 0)
                    {
                        
            for(int k = 0; k < 4; k ++)
                        
            if(sta[J].next[k]->flag == 0)
                        {
                            inc 
            = ( k != map(str[i]) );
                            updata(f[i 
            + 1][sta[J].next[k]->state], f[i][J] + inc);
                        }
                    }
                }
                
            //    for(int i = 0; i <= L; i ++)
            //    {printf("i=%d  ",i);for(int j = 0; j < indexx; j ++) printf("%d ",f[i%2][j]);puts("");}
                
                
            int ans = -1;
                
            for(int i = 0; i < indexx; i ++
                
            if(f[L][i] >= 0) updata(ans, f[L][i]);
                
            return ans;
            }

            int main()
            {
                
            int test = 0, n;
                
            while(scanf("%d"&n), n)
                {
                    init();
                    
            char dg[21];    
                    
            for(int i = 0; i < n; i ++)
                    {
                        scanf(
            "%s", dg);
                        insert(dg);
                    }
                    get_fail();
                    
            int ans = dp();
                    printf(
            "Case %d: %d\n",++test, ans);
                }
            }

            posted on 2009-09-09 02:24 superlong 閱讀(1016) 評論(1)  編輯 收藏 引用

            Feedback

            # re: Poj 3691 2010-10-25 11:10 acmer1183
            你寫的這個get_fail() 好像并是真正的get_fail,也是說fail指向的串并不是當前結點的子串。為什么要這樣弄呢?  回復  更多評論
              

            国产香蕉97碰碰久久人人| 久久夜色精品国产www| 日韩人妻无码一区二区三区久久| 777午夜精品久久av蜜臀| 国产精品久久久久久久| 久久人人爽人人爽AV片| 久久亚洲AV成人出白浆无码国产 | 国产高潮久久免费观看| 久久亚洲AV无码精品色午夜麻豆| 国内精品久久久久久99蜜桃| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 久久99国产精品久久99小说| 久久久久高潮毛片免费全部播放| 久久久WWW成人免费精品| 国产精品美女久久久m| 伊人久久亚洲综合影院| 久久综合久久综合久久| 亚洲国产精品无码久久一区二区| 久久久99精品一区二区| 色综合合久久天天综合绕视看| 亚洲精品无码久久久久sm| 午夜精品久久久内射近拍高清| 久久精品国产91久久麻豆自制| 性欧美大战久久久久久久久| 香蕉aa三级久久毛片| 精品久久久久久国产牛牛app| 91精品国产综合久久久久久| 伊人久久综合精品无码AV专区| 四虎久久影院| 亚洲国产日韩欧美综合久久| 亚洲国产成人久久综合一 | 国产成人精品久久亚洲| AV狠狠色丁香婷婷综合久久 | 无码人妻久久一区二区三区免费| 欧美亚洲日本久久精品| 久久久久国产精品嫩草影院| 久久精品亚洲欧美日韩久久| 久久99精品久久久久久齐齐| 韩国三级中文字幕hd久久精品 | 久久国产V一级毛多内射| 久久久亚洲精品蜜桃臀|