[bzoj1212][HNOI2004]L语言_AC自动机

L语言 bzoj-1212 HNOI-2004

题目大意：给你一个n个单词的集合，然后给你m条字符串。问每条字符串可以被理解的最长前缀。被理解当且仅当存在一种分割使得每一段都是集合里的元素。

注释：$1\le n,m\le 20$，长度不超过1M

想法：做了上一道，感觉这是个大水题... ...，我们将那个单词集合建立一个AC自动机，然后将每一个询问的字符串仍在字符串上跑，用bool型的dp。

dp[i]表示当前字符串前i位是否能被理解。

转移：如果j+1到i这段能被理解，那么dp[i]|=dp[j];

最后，附上丑陋的代码... ...

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 2000010

using namespace std;

char s[N];

int a[300][26];

bool end[300];

int n,m,cnt,fail[300],f[N];

void build(char *s)

{

    int now=0;

    int len=strlen(s);

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

    {

        if(!a[now][s[i]-'a'])

        {

            a[now][s[i]-'a']=++cnt;

        }

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

    }

    end[now]=true;

}

int main()

{

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

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

    {

        scanf("%s",s);

        build(s);

    }

    while(m--)

    {

        scanf("%s",s);

        int l=strlen(s);

        memset(f,0,sizeof f);

        f[0]=1;

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

        {

            if(f[i])

            {

                int now=0;

                for(int j=i;a[now][s[j]-'a'];j++)

                {

                    now=a[now][s[j]-'a'];

                    if(end[now])

                    {

                        f[j+1]|=f[i];

                    }

                }

            }

        }

        for(int i=l;~i;i--)

        {

            if(!f[i]) continue;

			printf("%d\n",i);

			break;

        }

    }

}

小结：ac自动接其实可以当Trie使.. ...虽然我写这东西是Trie图..

巴特西

[bzoj1212][HNOI2004]L语言_AC自动机_动态规划

最新文章

热门文章