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

            







            
	    
    




            






            

				

            




    
    







            
	   
	



亚洲色大成网站www久久九|
国产精品九九久久免费视频|
麻豆精品久久久一区二区|
亚洲精品美女久久久久99|
久久伊人中文无码|
久久国产精品视频|
99久久国产综合精品网成人影院|
久久亚洲欧美国产精品|
亚洲精品美女久久777777|
久久精品国产99久久久古代|
国内精品伊人久久久久777|
亚洲美日韩Av中文字幕无码久久久妻妇
|
国产精品中文久久久久久久|
蜜臀久久99精品久久久久久|
久久久久国产成人精品亚洲午夜|
久久青青草原精品国产软件|
久久笫一福利免费导航
|
91久久精品无码一区二区毛片|
欧美精品一本久久男人的天堂|
久久99热这里只有精品国产
|
一级A毛片免费观看久久精品|
亚洲日韩欧美一区久久久久我
|
久久妇女高潮几次MBA|
欧美午夜精品久久久久免费视
|
久久久精品国产sm调教网站|
国产精品久久久久久|
欧美一级久久久久久久大|
亚洲国产美女精品久久久久∴|
2022年国产精品久久久久|
久久久久国产日韩精品网站|
国产69精品久久久久观看软件
|
97精品国产97久久久久久免费|
久久精品99无色码中文字幕|
久久精品国产亚洲av麻豆蜜芽
|
国产成人精品综合久久久|
狠狠色综合网站久久久久久久高清
|
久久国产免费直播|
无码人妻精品一区二区三区久久|
国产午夜电影久久|
久久精品人人做人人爽97
|
91精品国产91久久|