本题是在text里面查找key word的增强版。由于这里有多个text。

那么就不能够简单把Trie的叶子标志记录改动成-1进行加速了，能够使用其它技术。我直接使用个vis数组记录已经訪问过的节点，达到加速效果，速度还算挺快的。

只是看discuss里面有人直接使用Trie，做出了140ms的速度，并且他的程序严格来说并不对。可见本题的数据非常水啊。Trie的时间效率肯定比AC自己主动机低，可是在数据非常水的特殊情况下。Trie的速度也能够非常快的。

注意两个细节：

1 病毒也须要安装顺序输出，不小心就遗漏了。这里害我错了几次。

2 还有就是题目的字符不确定是多少。使用33-94范围的字符測试答案正确的。

#include <stdio.h>

#include <string.h>

#include <queue>

#include <set>

#include <algorithm>

using namespace std;

const int MAX_N = 501;

const int MAX_WORD = 201;

const int MAX_M = 1001;

const int MAX_TXT = 10001;

const int MAX_V = 3;

const int ARR_SIZE = 94;

char virus[MAX_WORD], web[MAX_TXT];

int webNum[MAX_V];

int M, N;

inline int getIndex(char ch) { return ch - 33; }

struct Node

{

    int n, num, id;

    Node *fail;

    Node *arr[ARR_SIZE];

};

void clearNode(Node *rt)

{

    rt->n = 0;

    rt->num = 0;

    rt->id = 0;

    rt->fail = NULL;

    for (int i = 0; i < ARR_SIZE; i++)

    {

        rt->arr[i] = NULL;

    }

}

Node gPool[MAX_N*MAX_WORD], *Trie;

int gPoolID;

bool vis[MAX_N*MAX_WORD];    //怎么老是忘记使用visited技术的？

void insertTrie(char *virus, int num)

{

    Node *pCrawl = Trie;

    for (; *virus; virus++)

    {

        int id = getIndex(*virus);

        if (!pCrawl->arr[id])

        {

            pCrawl->arr[id] = &gPool[gPoolID++];

            clearNode(pCrawl->arr[id]);

            pCrawl->arr[id]->id = gPoolID-1;

        }

        pCrawl = pCrawl->arr[id];

    }

    pCrawl->n++;

    pCrawl->num = num;

}

void buildFail()

{

    queue<Node *> qu;

    qu.push(Trie);

    while (!qu.empty())

    {

        Node *p = qu.front(); qu.pop();

        for (int i = 0; i < ARR_SIZE; i++)

        {

            if (!p->arr[i]) continue;

            p->arr[i]->fail = Trie;

            Node *fail = p->fail;

            while (fail)

            {

                if (fail->arr[i])

                {

                    p->arr[i]->fail = fail->arr[i];

                    break;

                }

                fail = fail->fail;

            }

            qu.push(p->arr[i]);

        }

    }

}

int searchVirus(char *web)

{

    int n = 0;

    Node *pCrawl = Trie;

    memset(vis, 0, sizeof(bool)*(gPoolID+1));

    for (; *web; web++)

    {

        int i = getIndex(*web);

        while (!pCrawl->arr[i] && pCrawl != Trie) pCrawl = pCrawl->fail;

        if (pCrawl->arr[i])

        {

            pCrawl = pCrawl->arr[i];

            Node *p = pCrawl;

            while (p && !vis[p->id])//使用vis比直接检查数组值快捷方便

            {

                if (p->n) webNum[n++] = p->num;

                vis[p->id] = true;

                p = p->fail;

            }

            if (n == MAX_V) break;    //At most MAX_V virus one web

        }

    }

    return n;

}

int main()

{

    Trie = &gPool[0];

    while (scanf("%d", &N) != EOF)

    {

        gPoolID = 1;

        clearNode(Trie);

        getchar();

        for (int i = 1; i <= N; i++)

        {

            gets(virus);

            insertTrie(virus, i);

        }

        buildFail();

        scanf("%d", &M);

        getchar();

        int cnt = 0;

        for (int i = 1; i <= M; i++)

        {

            gets(web);

            int n = searchVirus(web);

            if (n)

            {

                cnt++;

                printf("web %d:", i);

                sort(webNum, webNum + n);//Watch out: order!

                for (int j = 0; j < n; j++)

                {

                    printf(" %d", webNum[j]);

                }

                putchar('\n');

            }

        }

        printf("total: %d\n", cnt);

    }

    return 0;

}