bzoj1212:[HNOI2004]L语言(trie+DP)

Author Avatar
Sakits 3月 08, 2018

题解

  trie和AC自动机之类一直都是薄弱方面,完蛋了QAQ
  设f(i)f(i)为长度为ii的前缀能否被识别。
  若第ii位的f(i)f(i)11,那么从第i+1i+1位开始在trie树上跑,若匹配长度为jj时跑到有单词的地方就将f(i+j)f(i+j)设为11,如果无法匹配了直接退出。
  因为单词长度非常小,所以完全可以承受从文章的每一位开始在trie上跑一个单词的长度。
  注意strlen是O(len)O(len)的,TLE了好多发QAQ
  TLE前卡了好多发常,找到strlen的问题AC后居然排到rk3232了…

代码

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=1233333;
struct poi{int nxt[26];}tree[maxn];
int n, m, tott, T, len;
int f[maxn], v[maxn];
char s[maxn];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void insert()
{
    int len=strlen(s+1), now=0;
    for(int i=1;i<=len;i++)
    if(tree[now].nxt[s[i]-'a']) now=tree[now].nxt[s[i]-'a'];
    else tree[now].nxt[s[i]-'a']=++tott, now=tott;
    v[now]=1;
}
inline void find(int x)
{
    int now=0;
    for(int j=1;j<=10 && x+j<=len;j++)
    if(tree[now].nxt[s[x+j]-'a'])
    {
        now=tree[now].nxt[s[x+j]-'a'];
        if(v[now]) f[x+j]=T;        
    }
    else return;
}
int main()
{
    read(n); read(m);
    for(int i=1;i<=n;i++) scanf("%s", s+1), insert();
    for(int i=1;i<=m;i++)
    {
        scanf("%s", s+1); 
        len=strlen(s+1); T++;
        int t=0, ans=0; f[0]=T; 
        for(int j=0;j<=len && t<=10;j++) 
        if(f[j]==T) t=0, ans=j, find(j); else t++;
        printf("%d\n", ans);
    }
}