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

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 閱讀(1283) 評論(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>
            
欧美三级资源在线|
亚洲主播在线|
欧美精品三区|
亚洲一区精品电影|
日韩一二三区视频|
黄色精品网站|
亚洲肉体裸体xxxx137|
欧美精品一区二区在线播放|
亚洲精选在线|
性感少妇一区|
在线观看日韩专区|
亚洲乱码精品一二三四区日韩在线|
亚洲成色777777在线观看影院|
久久xxxx|
欧美mv日韩mv亚洲|
久久全球大尺度高清视频|
欧美ed2k|
欧美激情视频在线免费观看 欧美视频免费一|
91久久精品一区二区别|
亚洲一二三区在线|
亚洲乱码一区二区|
亚洲欧美中文字幕|
一区二区三区 在线观看视频|
午夜精品一区二区三区在线播放
|
亚洲图片欧美一区|
亚洲日本免费|
美女精品一区|
欧美成人综合在线|
18成人免费观看视频|
小黄鸭精品密入口导航|
午夜精品久久久久久久99热浪潮|
玖玖玖国产精品|
蜜桃久久精品乱码一区二区|
1000部精品久久久久久久久|
久久高清免费观看|
亚洲国产一区二区精品专区|
国产精品视频专区|
欧美成人免费大片|
久久精精品视频|
亚洲一区亚洲|
亚洲一区二区三区视频|
亚洲国产欧美在线人成|
影音先锋欧美精品|
国产一区二区成人久久免费影院|
欧美日一区二区在线观看|
欧美成人综合一区|
欧美顶级艳妇交换群宴|
欧美成人免费在线|
欧美日本亚洲|
国产精品久99|
日韩一区二区免费高清|
91久久国产精品91久久性色|
亚洲国产99|
亚洲午夜91|
久久久久久久久伊人|
另类欧美日韩国产在线|
欧美激情视频在线播放|
国产精品人人做人人爽人人添|
国产精品高潮呻吟|
亚洲第一成人在线|
制服丝袜激情欧洲亚洲|
久久国产精品99久久久久久老狼|
久久久久久久国产|
亚洲精品自在久久|
欧美在线不卡|
国产精品乱码久久久久久|
狠久久av成人天堂|
亚洲自拍偷拍麻豆|
欧美肥婆在线|
午夜视黄欧洲亚洲|
欧美日韩国产高清|
韩日成人在线|
亚洲免费中文字幕|
久久久天天操|
亚洲免费大片|
久久久久久日产精品|
麻豆精品视频|
欧美三区在线观看|
国产日韩欧美中文|
正在播放日韩|
久久久爽爽爽美女图片|
亚洲二区三区四区|
午夜老司机精品|
欧美成人影音|
亚洲黄色在线视频|
午夜激情久久久|
亚洲国产高清自拍|
久久精品国产亚洲一区二区三区|
欧美/亚洲一区|
国产日韩欧美一区|
亚洲调教视频在线观看|
亚洲高清资源|
欧美日韩在线三级|
久久影院午夜论|
国产精品成av人在线视午夜片|
亚洲理伦在线|
亚洲人精品午夜|
欧美日韩成人综合|
亚洲日本中文|
欧美电影在线观看|
久久久午夜电影|
在线播放日韩|
美脚丝袜一区二区三区在线观看
|
亚久久调教视频|
亚洲天天影视|
国内激情久久|
欧美激情一区二区三区在线视频观看
|
亚洲精品中文在线|
亚洲第一综合天堂另类专|
美女黄网久久|
亚洲欧美日韩电影|
久久成人一区|
久久99在线观看|
国产精品一级二级三级|
日韩亚洲欧美高清|
一本色道久久综合亚洲精品不
|
99热这里只有成人精品国产|
欧美日韩一区二区在线播放|
亚洲欧美视频|
欧美激情1区2区3区|
欧美一二三区精品|
欧美精品啪啪|
亚洲国产精品久久久久秋霞不卡|
国产精品嫩草影院av蜜臀|
亚洲精品免费一二三区|
国产一区二区日韩精品欧美精品|
亚洲级视频在线观看免费1级|
久久久久久久一区二区三区|
欧美人与性动交cc0o|
亚洲成色777777女色窝|
激情文学一区|
欧美尤物一区|
亚洲视频你懂的|
国产日产精品一区二区三区四区的观看方式|
日韩视频在线一区|
欧美日本韩国一区|
亚洲黄色免费电影|
亚洲国产成人av在线|
麻豆乱码国产一区二区三区|
国产日韩成人精品|
美女999久久久精品视频|
亚洲福利在线看|
欧美一级黄色网|
亚洲国产aⅴ天堂久久|
欧美日韩一区二区国产|
午夜一级久久|
亚洲精品五月天|
女人天堂亚洲aⅴ在线观看|
亚洲人成网站精品片在线观看|
欧美性猛交xxxx乱大交蜜桃|
欧美高清在线|
欧美日韩黄色一区二区|
中文精品视频|
亚洲性感美女99在线|
在线视频精品|
久久久久高清|
久久精品国产久精国产爱|
欧美日韩视频一区二区|
欧美成人免费全部|
国产人久久人人人人爽|
亚洲麻豆一区|
一区二区三区产品免费精品久久75
|
亚洲在线一区二区三区|
一区精品久久|
欧美在线观看网站|
欧美一级久久|
国产精品久久97|
亚洲在线观看免费|
欧美在线高清|
亚洲国产精品毛片|
国产欧美日韩在线视频|
久久嫩草精品久久久精品一|
久久综合一区二区|
欧美影院视频|
中文欧美日韩|
欧美一区观看|
日韩视频永久免费观看|
好男人免费精品视频|
欧美日韩亚洲网|
夜夜嗨av一区二区三区|
国产一区二区三区高清|
午夜视频在线观看一区二区三区|
亚洲精品偷拍|
老司机午夜精品|
国产揄拍国内精品对白|
最新亚洲一区|
国产亚洲一区二区三区在线观看|
亚洲国产一区二区三区a毛片|
亚洲免费婷婷|
亚洲第一久久影院|
亚洲女人小视频在线观看|
欧美岛国激情|
狠狠久久综合婷婷不卡|
中日韩视频在线观看|
欧美夫妇交换俱乐部在线观看|
亚洲一区三区视频在线观看|
欧美韩国一区|
精品二区久久|
久久se精品一区精品二区|
在线亚洲一区二区|