• <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++博客 :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
              74 Posts :: 0 Stories :: 5 Comments :: 0 Trackbacks

            公告

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

            常用鏈接

            留言簿(4)

            我參與的團隊

            搜索

            •  

            最新隨筆

            最新評論

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

            閱讀排行榜

            評論排行榜

            #include <iostream>
            #include 
            <string.h>
            using namespace std;

            struct tree
            {
                tree 
            *next[26], *fail;
                
            int flag, len, ;
            };

            tree 
            *root, *p;
            tree arr[
            500001];
            int  indexx;
            char letter = 'a';

            void newn()
            {
                arr[indexx].fail 
            = NULL;
                arr[indexx].flag 
            = 0;
                arr[indexx].len 
            = -1;
                
            for(int i = 0; i < 26; i ++) arr[indexx].next[i] = 0;
            }

            void insert(char ch[], int w)
            {
                p 
            = root;
                
            int tmp, i = 0;
                
            while(ch[i])
                {
                    tmp 
            = ch[i] - letter;
                    
            if(p->next[tmp] == 0)
                    {
                        newn();
                        p
            ->next[tmp] = &arr[indexx ++];
                        p
            ->next[tmp]->len = p->len + 1;
                    }
                    p 
            = p->next[tmp];
                    i 
            ++;
                }
                
            if(!p->flag)
                    p
            ->flag = w;
            }

            tree 
            *que[500005];

            void get_fail()
            {
                p
            =root;
                p
            ->fail = root;
                
            int open = 0, close = -1, i;
                que[
            0= p;
                
            while(close < open)
                {
                    p 
            = que[++ close];
                    
            for(i = 0; i < 26; 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];
                        }
                    }
                }
            }

            int ans[2][100005];
            int pos[100005];

            void query(char ch[])
            {
                p 
            = root;
                tree 
            *q;
                
            int t, i = 0;
                
            while(ch[i])
                {
                    t 
            = ch[i] - letter;
                    p 
            = p->next[t];
                    q 
            = p;
                    
            while(q != root && q->fail )
                    {
                        
            if(q->flag)
                        {
                            ans[
            0][q->flag] ++;
                            
            if(i - pos[q->flag] > q->len)
                            {
                                ans[
            1][q->flag] ++;
                                pos[q
            ->flag] = i;
                            }
                        }
                        q 
            = q->fail;
                    }
                    i 
            ++;
                }
            }

            int search(char ch[])
            {
                p 
            = root;
                
            int tmp, i = 0;
                
            while(ch[i])
                {
                    tmp 
            = ch[i] - letter;
                    p 
            = p->next[tmp];
                    i 
            ++;
                }
                
            return p->flag;
            }

            void init()
            {
                indexx 
            = 0;
                newn();
                root 
            = &arr[indexx ++];
                memset(ans, 
            0sizeof(ans));
                memset(pos, 
            -1sizeof(pos));
            }

            char str[100005];
            char dic[100005][7];
            int  typed[100005];

            int main()
            {
                
            int test = 0;
                
            while(scanf("%s", str) != EOF)
                {
                    
            int n, i;
                    init();
                    scanf(
            "%d"&n);
                    
            for(i = 1; i <= n; i ++)
                    {
                        scanf(
            "%d %s"&typed[i], dic[i]);
                        insert(dic[i], i);
                    }
                    get_fail();
                    query(str);
                    printf(
            "Case %d\n",++test);
                    
            for(i = 1; i <= n; i ++)
                    {
                        
            int id = search(dic[i]);
                        printf(
            "%d\n", ans[typed[i]][id]);
                    }
                    puts(
            "");
                }
            }

            posted on 2009-09-08 12:17 superlong 閱讀(463) 評論(0)  編輯 收藏 引用
            久久精品免费一区二区三区| 岛国搬运www久久| 久久久久久国产精品免费免费| 丁香久久婷婷国产午夜视频| 久久强奷乱码老熟女网站| 国产精品久久久久久久久久影院| 精品久久久久久综合日本| 国产成人久久激情91| 色综合久久天天综合| 久久久久久午夜精品| 精品久久久久国产免费 | 亚洲欧美精品一区久久中文字幕| 久久久久久国产精品美女| 久久午夜伦鲁片免费无码| 国产成人精品久久亚洲高清不卡| 欧美成a人片免费看久久| av无码久久久久不卡免费网站| 久久国产成人午夜aⅴ影院| 久久棈精品久久久久久噜噜| 亚洲精品97久久中文字幕无码| 久久久无码精品亚洲日韩按摩| 欧美激情精品久久久久久久九九九| 久久天堂AV综合合色蜜桃网| 天天影视色香欲综合久久| 精品999久久久久久中文字幕| 久久精品久久久久观看99水蜜桃| 一级做a爰片久久毛片16| 国内精品久久久久影院优| 久久亚洲私人国产精品vA| 亚洲国产精品热久久| 国产成人精品久久免费动漫 | 国产精品久久久久一区二区三区 | 18岁日韩内射颜射午夜久久成人| 久久WWW免费人成一看片| 久久高清一级毛片| 婷婷综合久久狠狠色99h| 九九精品久久久久久噜噜| 久久黄视频| 久久成人18免费网站| 亚洲一区中文字幕久久| 成人免费网站久久久|