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

    
            

            




            







												


        




            
	
		
            
			


            
posts - 33, 
comments - 33, 
trackbacks - 0


            
	

            


            
	
					


            
	
	
            AC自動機用于多模式串匹配

              1#include <stdio.h>
              2#include <string.h>
              3#include <queue>
              4using namespace std;
              5
              6const int N = 500005;
              7
              8struct Trie
              9{
             10    int flag;
             11    int fail;
             12    int next[26];
             13
             14    void Init()
             15    {
             16        flag = 0;
             17        fail = -1;
             18        for(int i = 0; i < 26; ++i)
             19            next[i] = 0;
             20    }
             21}            ;
             22
             23Trie trieTrees[N];
             24int treeCnt;
             25char strs[1000005];
             26int n;
             27
             28void Insert(char* _str)
             29{
             30    int rt = 0;
             31    while(*_str != 0)
             32    {
             33        int t = *_str - 'a';
             34        if(trieTrees[rt].next[t] == 0)
             35        {
             36            trieTrees[++treeCnt].Init();
             37            trieTrees[rt].next[t] = treeCnt;
             38        }
             39        rt = trieTrees[rt].next[t];
             40        ++_str;
             41    }
             42    trieTrees[rt].flag++;
             43}
             44
             45
             46void BFS()
             47{
             48    queue<int> Queue;
             49    int rt = 0;
             50    int p,q;
             51    Queue.push(0);
             52    while(!Queue.empty())
             53    {
             54        int now = Queue.front();
             55        Queue.pop();
             56        for(int t = 0; t < 26; ++t)
             57        {
             58            if(trieTrees[now].next[t])
             59            {
             60                p = trieTrees[now].fail;
             61                q = trieTrees[now].next[t];
             62                while(p !=-1 && trieTrees[p].next[t] == NULL)
             63                    p = trieTrees[p].fail;
             64                if(p == -1)
             65                    trieTrees[q].fail = 0;
             66                else
             67                    trieTrees[q].fail = trieTrees[p].next[t];
             68                Queue.push(q);
             69            }
             70        }
             71    }
             72}
             73
             74int Match(char *_str)
             75{
             76    int ret = 0;
             77    int rt = 0;
             78    int t,p;
             79    while(*_str)
             80    {
             81        t = *_str - 'a';
             82        if(trieTrees[rt].next[t])
             83            rt = trieTrees[rt].next[t];
             84        else
             85        {
             86            p = trieTrees[rt].fail;
             87            while(p != -1 && (!trieTrees[p].next[t]))
             88                p = trieTrees[p].fail;
             89            if(p == -1)
             90                rt = 0;
             91            else
             92                rt = trieTrees[p].next[t];
             93        }
             94        p = rt;
             95        while(p != 0&& trieTrees[p].flag)
             96        {
             97            if(trieTrees[p].flag)
             98            {
             99                ret += trieTrees[p].flag;
            100                trieTrees[p].flag = 0;
            101            }
            102            p = trieTrees[p].fail;
            103        }
            104        ++_str;
            105    }
            106    return ret;
            107}
            108
            109void Test()
            110{
            111    scanf("%d",&n);
            112    treeCnt = 0;
            113    trieTrees[0].Init();
            114    for(int i = 0; i < n; ++i)
            115    {
            116        while(gets(strs),strcmp(strs,"") == 0 );
            117        Insert(strs);
            118    }
            119    BFS();
            120    gets(strs);
            121    int ret = Match(strs);
            122    printf("%d\n",ret);
            123}
            124
            125int main()
            126{
            127    //freopen("data.txt","r",stdin);
            128    int testcase;
            129    scanf("%d",&testcase);
            130    for(int i = 0; i < testcase; ++i)
            131        Test();
            132    return 0;
            133}

            
	
            posted on 2012-03-29 18:15 bennycen 閱讀(1271) 評論(0)  編輯 收藏 引用  所屬分類: 算法題解 
            

            







            
	    
    




            






            

				

            




    
    







            
	   
	



伊人色综合久久天天网|
午夜精品久久影院蜜桃|
久久久国产乱子伦精品作者|
国产一级做a爰片久久毛片|
国产成人久久精品激情|
久久精品这里只有精99品|
99久久综合国产精品免费|
久久精品国产99国产电影网|
久久免费99精品国产自在现线|
尹人香蕉久久99天天拍|
精品午夜久久福利大片|
亚洲国产视频久久|
国产A级毛片久久久精品毛片|
模特私拍国产精品久久|
国产精品一区二区久久精品无码|
久久人人添人人爽添人人片牛牛|
免费观看久久精彩视频|
国内精品人妻无码久久久影院导航|
青青草国产精品久久|
色欲久久久天天天综合网|
久久99精品九九九久久婷婷|
亚洲国产精品无码久久久蜜芽
|
久久国产一片免费观看|
久久精品www人人爽人人|
综合人妻久久一区二区精品|
欧美精品福利视频一区二区三区久久久精品|
色狠狠久久AV五月综合|
99精品国产99久久久久久97|
久久九色综合九色99伊人|
91精品国产91久久久久久|
99久久婷婷免费国产综合精品|
伊人久久大香线蕉亚洲|
久久AV高潮AV无码AV|
97精品伊人久久大香线蕉|
久久精品免费全国观看国产|
亚洲午夜无码久久久久小说
|
久久婷婷是五月综合色狠狠|
国产免费福利体检区久久|
日本三级久久网|
国产ww久久久久久久久久|
久久久精品国产亚洲成人满18免费网站|