青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(1287) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 算法題解
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

    • <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>
            
久久久久久久综合狠狠综合|
亚洲国产高潮在线观看|
国产综合色在线|
国产精品自拍三区|
国产伦精品一区二区三区高清|
欧美午夜不卡|
国产无一区二区|
亚洲精华国产欧美|
亚洲专区一区二区三区|
久久久国产91|
亚洲精品国产无天堂网2021|
亚洲一区二区视频在线|
欧美在线观看日本一区|
免费视频久久|
国产精品国码视频|
亚洲第一在线综合网站|
国产精品99久久久久久久久|
久久成人免费|
亚洲日本激情|
欧美在线视频不卡|
欧美欧美全黄|
国产亚洲欧洲一区高清在线观看|
亚洲高清123|
欧美亚洲三区|
亚洲精华国产欧美|
久久av在线|
国产精品免费网站|
欧美日韩免费视频|
欧美一区精品|
欧美激情第一页xxx|
欧美高清hd18日本|
夜色激情一区二区|
老司机aⅴ在线精品导航|
99在线热播精品免费99热|
久久久久久久精|
久久高清免费观看|
欧美日韩亚洲另类|
亚洲国产精品一区二区第一页|
亚洲自拍啪啪|
亚洲国产一区二区视频|
欧美一级二区|
国产精品美腿一区在线看|
日韩视频在线免费|
免费日韩成人|
久久久999|
国产午夜精品全部视频在线播放|
亚洲特级毛片|
99精品99久久久久久宅男|
欧美第十八页|
亚洲欧洲日韩女同|
欧美成人久久|
久久香蕉精品|
在线日本欧美|
免费看成人av|
久久久久久久综合|
黄色精品在线看|
久久亚洲春色中文字幕|
欧美在线观看www|
国产在线精品二区|
久久九九99视频|
欧美一区视频|
狠狠色丁香婷婷综合|
久久亚洲色图|
麻豆国产精品777777在线|
在线免费一区三区|
亚洲大片av|
欧美日韩精品一区二区三区四区|
一本大道久久精品懂色aⅴ|
亚洲毛片一区二区|
欧美视频一区二区三区在线观看
|
欧美理论片在线观看|
亚洲精品欧洲|
99综合电影在线视频|
国产精品扒开腿爽爽爽视频|
亚洲永久免费观看|
欧美在线视频a|
亚洲黄网站黄|
亚洲美女电影在线|
国产精品一区免费视频|
久久九九久精品国产免费直播|
欧美有码视频|
亚洲精品中文字|
亚洲一区二区av电影|
狠狠色狠狠色综合日日tαg|
亚洲国产成人不卡|
国产精品美女久久久浪潮软件|
久久狠狠一本精品综合网|
久久婷婷国产综合尤物精品|
一本一本久久a久久精品牛牛影视|
一区二区三区免费看|
91久久精品国产91久久|
午夜天堂精品久久久久|
亚洲一区二区动漫|
一区二区三区四区在线|
国产精品久久国产愉拍|
亚洲一区精品在线|
亚洲大片在线观看|
国产精品国产精品|
免费不卡中文字幕视频|
欧美色视频在线|
欧美va亚洲va香蕉在线|
欧美亚洲不卡|
欧美a级片网|
国产精品影音先锋|
欧美激情一区二区三区四区|
国产精品一区二区你懂得|
亚洲国产高清一区|
国产一级揄自揄精品视频|
99爱精品视频|
亚洲国产裸拍裸体视频在线观看乱了|
在线视频精品一区|
亚洲精品乱码久久久久久久久|
亚洲午夜激情|
一区二区欧美国产|
美日韩在线观看|
久久久久久久综合日本|
欧美视频免费在线观看|
欧美激情免费观看|
在线欧美日韩|
欧美主播一区二区三区美女 久久精品人|
亚洲精品偷拍|
老牛影视一区二区三区|
另类综合日韩欧美亚洲|
国产真实精品久久二三区|
亚洲欧美日韩在线一区|
亚洲欧美视频一区|
国产精品久久久久久久久婷婷|
亚洲精品久久久久久久久|
亚洲精选在线|
欧美成人在线影院|
欧美激情在线免费观看|
尤物99国产成人精品视频|
欧美伊人久久久久久午夜久久久久|
亚洲在线观看视频|
国产精品vvv|
亚洲午夜小视频|
欧美一级大片在线观看|
国产乱码精品一区二区三|
亚洲欧美成人一区二区在线电影|
亚洲制服av|
国产精品夜色7777狼人|
亚洲欧美电影院|
久久精品国产亚洲一区二区|
黑人操亚洲美女惩罚|
久久久亚洲一区|
欧美成人午夜激情视频|
最近中文字幕日韩精品|
欧美精品二区|
一区二区高清视频|
午夜视频精品|
尤物精品国产第一福利三区|
女生裸体视频一区二区三区|
亚洲精品在线观看视频|
性色av一区二区三区在线观看|
国产欧亚日韩视频|
久久精品av麻豆的观看方式
|
日韩视频免费观看高清完整版|
亚洲国产精品久久久久久女王|
久久久久久电影|
亚洲国产精品小视频|
亚洲午夜激情网页|
国产精品亚洲综合色区韩国|
久久国产精品99国产精|
欧美成人中文|
亚洲一区中文|
在线精品亚洲|
欧美日韩一视频区二区|
午夜日本精品|
亚洲第一伊人|
香蕉成人久久|
最新亚洲一区|
国产欧美精品一区|
欧美大片专区|
久久国产视频网站|
日韩一区二区精品葵司在线|
久久久久久久久久码影片|
日韩亚洲欧美一区|
国产一区二三区|
欧美调教视频|
麻豆91精品|
校园春色国产精品|
亚洲免费观看|
欧美成人午夜免费视在线看片|
亚洲无线视频|
亚洲全部视频|
国产一区二区三区成人欧美日韩在线观看
|
久久天堂国产精品|
在线一区二区三区四区|
亚洲电影免费|
国产一区二区三区电影在线观看|
欧美高清一区|
久久视频在线看|
翔田千里一区二区|
99国产精品久久久久久久成人热
|
亚洲第一福利社区|
久久久之久亚州精品露出|
午夜精品网站|
亚洲色在线视频|
亚洲精选久久|
亚洲精品一区二区三区不|