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

            







            
	    
    




            






            

				

            




    
    







            
	   
	



欧洲精品久久久av无码电影|
2021国内精品久久久久久影院|
久久精品成人国产午夜|
99久久精品国产毛片|
久久精品国产亚洲一区二区三区|
欧美激情精品久久久久久久九九九|
国产精品成人久久久|
国产精品久久久久无码av
|
欧美久久精品一级c片片|
久久天天日天天操综合伊人av|
AV无码久久久久不卡蜜桃|
青青青青久久精品国产h|
精品国产日韩久久亚洲|
伊人色综合久久|
人妻精品久久久久中文字幕一冢本|
久久se精品一区二区影院
|
国产成人久久精品一区二区三区
|
青青草国产精品久久久久|
久久91精品国产91|
国产激情久久久久影院小草|
久久这里的只有是精品23|
国产精品久久久久久久久久免费|
国产成人精品久久|
一本大道久久香蕉成人网|
日韩精品国产自在久久现线拍|
久久丫精品国产亚洲av|
国内精品久久久久影院老司|
精品久久久久久无码人妻蜜桃|
成人久久综合网|
久久w5ww成w人免费|
午夜精品久久久久久99热|
精品久久久久久久久免费影院|
久久综合亚洲色HEZYO国产|
色综合久久久久网|
日本免费久久久久久久网站|
久久99精品国产|
青青青青久久精品国产h|
久久精品免费观看|
久久99国产精品久久99果冻传媒|
国产亚洲欧美成人久久片|
精品一区二区久久|