bzoj3940

AC自动机

复习一下。。。可惜又写错了

我们发现就是把单词建成ac自动机，然后把串在ac自动机上跑一遍，每到一个单词结束点就删除，删除是利用栈，每次弹出单词长度个字符就可以了

发现两个小问题，strlen很慢，不能写在循环里，danger必须在构造fail时全部传递好，否则在匹配时跑fail会达到n^2

至于这里danger为什么不转移，我也不是很清楚。。。大概是因为使用了trie图优化，并且不是统计单词出现次数，只是希望尽量找到靠前的单词删除

#include<bits/stdc++.h>

using namespace std;

const int N = ;

int n, top;

char s[N], t[N], st[N];

int mark[N], last[N];

struct AC {

    int root, cnt;

    int danger[N], child[N][], fail[N];

    void insert()

    {

        int now = root, len = strlen(t);

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

        {

            int p = t[i] - 'a';

            if(child[now][p] == ) child[now][p] = ++cnt;

            now = child[now][p];

        }

        danger[now] = strlen(t);

    }

    void build_fail()

    {

        queue<int> q;

        for(int i = ; i < ; ++i) if(child[root][i]) q.push(child[root][i]);

        while(!q.empty())

        {

            int u = q.front();

            q.pop();

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

            {

                if(child[u][i] == ) child[u][i] = child[fail[u]][i];

                else

                {

                    fail[child[u][i]] = child[fail[u]][i];

                    q.push(child[u][i]);

                }

            }

        }

    }

    void put_string()

    {

        int now = root, len = strlen(s);

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

        {

            st[++top] = s[i];

            now = child[now][s[i] - 'a'];

            last[top] = now;

            top -= danger[now];

            now = last[top];

        }

    }

} ac;

int main()

{

    scanf("%s%d", s, &n);

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

    {

        scanf("%s", t);

        ac.insert();

    }

    ac.build_fail();

    ac.put_string();

    int cnt = ;

    for(int i = ; i <= top; ++i) printf("%c", st[i]);

    return ;

}

巴特西

bzoj3940

最新文章

热门文章