bzoj 1212: [HNOI2004]L语言

.

题意：给出一个词典和几篇文章，问每篇文章最多匹配多长。
题解：trie+暴力dp
2亿的复杂度居然能过。。666

#include<bits/stdc++.h>
using namespace std;

struct trie
{
    bool s;
    int c[26];
}tr[210];
int n,m,num=0;
char s[1000010];
bool f[1000010];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%s",s);
        int len=strlen(s),now=0;
        for(int i=0;i<len;i++)
        {
            if(!tr[now].c[s[i]-'a'])
            tr[now].c[s[i]-'a']=++num;
            now=tr[now].c[s[i]-'a'];
        }
        tr[now].s=1;
    }
    for(int i=0;i<m;i++)
    {
        scanf("%s",s+1);
        int len=strlen(s+1);
        memset(f,0,sizeof(f));
        f[0]=1;
        int ans=0;
        for(int i=0;i<len;i++)
        {
            if(f[i])
            {
                int now=0;
                for(int j=i+1;j<=len;j++)
                {
                    if(!tr[now].c[s[j]-'a'])
                    break;
                    now=tr[now].c[s[j]-'a'];
                    if(tr[now].s)
                    f[j]=1;
                }
                ans=i;
            }
        }
        if(f[len])
        ans=len;
        printf("%d\n",ans);
    }
}