• <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)  編輯 收藏 引用
            久久97久久97精品免视看秋霞| 伊人久久大香线蕉av不变影院| 久久精品无码午夜福利理论片| 热久久最新网站获取| 久久精品国产亚洲精品2020| 久久无码av三级| 久久精品一区二区三区中文字幕| 三级片免费观看久久| 无码国产69精品久久久久网站| AV无码久久久久不卡网站下载| 日本免费久久久久久久网站| 亚洲伊人久久综合影院| 久久精品黄AA片一区二区三区| 欧美国产精品久久高清| 久久精品国产网红主播| 色99久久久久高潮综合影院| 亚洲精品无码久久久久去q| 国产精品伊人久久伊人电影| 热99RE久久精品这里都是精品免费 | 97超级碰碰碰碰久久久久| 97香蕉久久夜色精品国产| 精品一区二区久久| 久久久久久久女国产乱让韩| 国内精品伊人久久久久| 精品国产乱码久久久久久呢 | 青青青青久久精品国产| 欧美日韩精品久久免费| 久久国产精品一区| 精品久久久久久无码专区不卡| 亚洲美日韩Av中文字幕无码久久久妻妇| 国产亚洲美女精品久久久久狼| 久久精品青青草原伊人| 精品国产乱码久久久久软件| 国产精品久久久久一区二区三区| 国产精品免费看久久久| 欧美黑人又粗又大久久久| 国产成人无码精品久久久性色 | 久久精品国产亚洲AV麻豆网站| 亚洲精品NV久久久久久久久久| 久久电影网| 少妇被又大又粗又爽毛片久久黑人 |