• <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自動(dòng)機(jī)用于多模式串匹配

              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 閱讀(1281) 評論(0)  編輯 收藏 引用  所屬分類: 算法題解 
            

            







            
	    
    




            






            

				

            




    
    







            
	   
	



久久精品天天中文字幕人妻
|
蜜桃麻豆www久久国产精品|
亚洲国产精品久久电影欧美|
欧美精品国产综合久久|
久久久久久午夜成人影院
|
久久久99精品成人片中文字幕|
色综合久久天天综线观看|
97精品伊人久久久大香线蕉|
国产99精品久久|
亚洲午夜福利精品久久|
99久久国产综合精品麻豆|
午夜精品久久久久久影视777
|
久久免费视频网站|
理论片午午伦夜理片久久|
狠狠狠色丁香婷婷综合久久五月|
亚洲AⅤ优女AV综合久久久|
久久w5ww成w人免费|
中文字幕久久亚洲一区|
99久久精品国产一区二区蜜芽|
精品人妻伦九区久久AAA片69|
亚洲国产成人久久综合碰碰动漫3d|
亚洲人AV永久一区二区三区久久
|
久久久精品人妻一区二区三区蜜桃
|
国产高清美女一级a毛片久久w|
精品无码久久久久国产动漫3d|
美女久久久久久|
久久久久亚洲AV无码去区首|
国内精品久久久久久不卡影院|
777米奇久久最新地址|
麻豆亚洲AV永久无码精品久久|
久久婷婷色综合一区二区|
亚洲欧美国产日韩综合久久|
欧美激情精品久久久久久久|
久久国产香蕉视频|
久久人人爽人人精品视频|
国产成人香蕉久久久久|
久久久WWW成人免费毛片|
色综合色天天久久婷婷基地|
国产精品久久久久久吹潮|
久久人爽人人爽人人片AV|
久久九九精品99国产精品|