HDU 3065

题目大意

暂无

题目解法

暂无

RTFC

#include <cctype>
#include <cstdio>
#include <cstring>
struct node
{
    node *trans[26], *fail;
    int id;
} nodes[50010], virt;
node *root;
int tot;
node *new_node() { return &nodes[tot++]; }
node *que[50010];
void insert(char *str, int idx)
{
    node *cur = root;
    for (; *str; str++)
    {
        if (cur->trans[*str - 'A'] == 0) cur->trans[*str - 'A'] = new_node();
        cur = cur->trans[*str - 'A'];
    }
    cur->id = idx;
}
void getFail()
{
    int h = 0, t = 0;
    que[t++] = root;
    while (h < t)
    {
        node *cur = que[h++];
        for (int i = 0; i < 26; i++)
        {
            node *f = cur->fail;
            while (f->trans[i] == 0) f = f->fail;
            f = f->trans[i];
            if (cur->trans[i])
                (que[t++] = cur->trans[i])->fail = f;
            else
                cur->trans[i] = f;
        }
    }
}
char buf[2000010];
char virs[1010][55];
int cnt[1010];
void run(char *ch)
{
    node *cur = root;
    for (; *ch; ch++)
        if (isupper(*ch))
        {
            while (cur->trans[*ch - 'A'] == 0) cur = cur->fail;
            cur = cur->trans[*ch - 'A'];
            node *tmp = cur;
            for (; tmp; tmp = tmp->fail)
                cnt[tmp->id]++;
        }
        else
            cur = root;
}
int main()
{
    int n;
    while (~scanf("%d", &n))
    {
        memset(cnt, 0, sizeof(cnt));
        memset(nodes, 0, sizeof(nodes));
        tot = 0;
        (root = new_node())->fail = &virt;
        for (int i = 0; i < 26; i++) virt.trans[i] = root;
        for (int i = 1; i <= n; i++)
        {
            scanf("%s", virs[i]);
            insert(virs[i], i);
        }
        getFail();
        scanf("%s", buf);
        int len = strlen(buf);
        run(buf);
        for (int i = 1; i <= n; i++)
            if (cnt[i])
                printf("%s: %d\n", virs[i], cnt[i]);
    }
    return 0;
}