toj 4063 单词(AC自动机)

题目：

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成的。

但小张发现一个单词会在论文中出现很多次,他想知道每个单词分别在论文中出现了多少次。

输入

第一行一个整数N,表示有N个单词。接下来N行每行一个单词,每个单词都由小写字母('a'-'z')组成。(N≤200, 单词总长度不超过10⁶)

输出

输出N个整数,第i行的数表示第i个单词在文章中出现了多少次。

样例输入

3

a

aa

aaa

样例输出

提示

可以将论文内容看做'a aa aaa'。

题解：可以用AC自动机来解，插入单词的时候，在每个字母位置计数器加1，统计每个单词结尾的计数器即可。

代码如下：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 250

#define maxn 1000100

struct TNode

{

    TNode *fail;

    TNode *next[];

    int cnt;

    TNode()

    {

        cnt = ;

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

            next[i] = NULL;

        fail = NULL;

        return;

    }

};

TNode *root;

int Tcnt;

TNode *TQ[N];

void Insert(const char *s)

{

    int len = strlen(s);

    TNode *p = root;

    for(int i = ; i < len; i++)

    {

        if(p->next[s[i]-'a'] == NULL)

            p->next[s[i]-'a'] = new TNode();

        p = p->next[s[i]-'a'];

        p->cnt++;

    }

    TQ[Tcnt++] = p;

    return ;

}

TNode *queue[maxn];

void build_ac_automation()

{

    int front, rear;

    front = rear = ;

    root -> fail = root;

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

    {

        if(root->next[i] != NULL)

        {

            root ->next[i]->fail = root;

            queue[rear++] = root->next[i];

        }

    }

    while(front < rear)

    {

        TNode *p = queue[front++];

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

        {

            TNode *q = p->fail;

            if(p->next[i] == NULL) continue;

            queue[rear++] = p->next[i];

            while(q->next[i] == NULL && q!=root)

                q = q->fail;

            if(q->next[i] == NULL)

                p->next[i]->fail = root;

            else p->next[i]->fail = q->next[i];

        }

    }

    while(rear>){

        --rear;

        queue[rear]->fail->cnt += queue[rear]->cnt;

    }

    return ;

}

char s[];

int main()

{

    int T,n;

    while(~scanf("%d", &n))

    {

        Tcnt = ;

        root = new TNode();

        scanf("%d", &n);

        for(int i = ; i < n; i++)

        {

            scanf("%s", s);

            Insert(s);

        }

        build_ac_automation();

        for(int i = ; i < n; i++)

            printf("%d\n", TQ[i]->cnt);

    }

    return ;

}

巴特西

toj 4063 单词(AC自动机)

输入

输出

样例输入

样例输出

提示

最新文章

热门文章