• <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)  編輯 收藏 引用  所屬分類: 算法題解 
            

            







            
	    
    




            






            

				

            




    
    







            
	   
	



97精品国产97久久久久久免费|
国产美女久久精品香蕉69|
99久久精品这里只有精品|
久久91精品国产91久久户|
国产呻吟久久久久久久92|
国产精品久久久久久久人人看|
久久综合国产乱子伦精品免费|
久久美女人爽女人爽|
久久性精品|
久久精品中文闷骚内射|
人妻系列无码专区久久五月天|
国产69精品久久久久9999APGF
|
yy6080久久|
一本色道久久88加勒比—综合|
久久精品综合网|
久久九九全国免费|
少妇内射兰兰久久|
欧美一级久久久久久久大片|
狠狠狠色丁香婷婷综合久久五月|
婷婷国产天堂久久综合五月|
久久99国产精品成人欧美|
国产成人精品白浆久久69|
一本色道久久88精品综合|
欧美精品丝袜久久久中文字幕
|
欧美日韩精品久久久免费观看|
狠狠色丁香久久婷婷综合五月|
看全色黄大色大片免费久久久
|
午夜久久久久久禁播电影|
国产真实乱对白精彩久久|
久久精品国内一区二区三区|
久久久女人与动物群交毛片|
性做久久久久久久久|
久久影院久久香蕉国产线看观看|
超级碰久久免费公开视频|
91麻精品国产91久久久久|
久久综合丝袜日本网|
国产成人香蕉久久久久|
久久99亚洲综合精品首页|
久久精品国产亚洲7777|
久久久噜噜噜久久中文字幕色伊伊|
97久久精品人人做人人爽|