BZOJ1212: [HNOI2004]L语言

传送门: http://www.lydsy.com/JudgeOnline/problem.php?id=1212

Solution

注意到单词长度很小,用Trie树+DP可以水过,f[i]表示能否匹配到第i位,若f[i]==1,则从i+1位置继续匹配,因为单词长度≤10,暴力跑就行了.
AC自动机是什么?能吃吗?.

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=(1<<20)+100;
int n,m,len,cnt,ans;
int c[2005][26],f[N],end[N];
char s[N];
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%s",s+1);
        len=strlen(s+1);
        int now=0;
        for (int j=1;j<=len;j++){
            if (c[now][s[j]-'a']) now=c[now][s[j]-'a'];
            else now=c[now][s[j]-'a']=++cnt;
        }
        end[now]=1;
    }
    for (int i=1;i<=m;i++){
        scanf("%s",s+1);
        len=strlen(s+1);
        memset(f,0,sizeof f);
        f[0]=1; ans=0;
        for (int j=0;j<=len;j++){
            if (!f[j]) continue; else ans=j;
            for (int k=j+1,now=0;k<=len;k++){
                now=c[now][s[k]-'a'];
                if (!now) break;
                if (end[now]) f[k]=1;
            }
        }
        printf("%d\n",ans);
    }
}