1212: [HNOI2004]L语言

(自认为自己的trie很牛逼然而....这是模板题然后吃饭的时候想到了一种比较快的方法然后发现you bug 再看了qko学弟的博客后我才发现数据匹配只有200个....直接暴力往后走最远的位置就行了啊....自己还差点写AC自动机太菜了.....

1212: [HNOI2004]L语言

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1915 Solved: 883
[Submit][Status][Discuss]

Description

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。一段文章T是由若干小写字母构成。一个单词W也是由若干小写字母构成。一个字典D是若干个单词的集合。我们称一段文章T在某个字典D下是可以被理解的，是指如果文章T可以被分成若干部分，且每一个部分都是字典D中的单词。例如字典D中包括单词{‘is’, ‘name’, ‘what’, ‘your’}，则文章‘whatisyourname’是在字典D下可以被理解的因为它可以分成4个单词：‘what’, ‘is’, ‘your’, ‘name’，且每个单词都属于字典D，而文章‘whatisyouname’ 在字典D下不能被理解，但可以在字典D’=D+{‘you’}下被理解。这段文章的一个前缀‘whatis’，也可以在字典D下被理解而且是在字典D下能够被理解的最长的前缀。给定一个字典D，你的程序需要判断若干段文章在字典D下是否能够被理解。并给出其在字典D下能够被理解的最长前缀的位置。

Input

输入文件第一行是两个正整数n和m，表示字典D中有n个单词，且有m段文章需要被处理。之后的n行每行描述一个单词，再之后的m行每行描述一段文章。其中1<=n, m<=20，每个单词长度不超过10，每段文章长度不超过1M。

Output

对于输入的每一段文章，你需要输出这段文章在字典D可以被理解的最长前缀的位置。

Sample Input

4 3
is
name
what
your
whatisyourname
whatisyouname
whaisyourname

Sample Output

14
6
0 整段文章’whatisyourname’都能被理解
前缀’whatis’能够被理解
没有任何前缀能够被理解

#include <bits/stdc++.h>
#define N 2000005
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
typedef struct node{
    int a[26];int sum;
}node;
node d[405];
int cnt,root;
int csh(){
    cnt++;d[cnt].sum=0;
    for(int i=0;i<26;i++) d[cnt].a[i]=0;
    return cnt;
}
void insert(char str[]){
    int len=strlen(str);int temp=root;
    for(int i=0;i<len;i++){
        int t=str[i]-'a';
        if(d[temp].a[t]==0){
            d[temp].a[t]=csh();
        }
        temp=d[temp].a[t];
        if(i==len-1) d[temp].sum=1;
    }
}
char s1[N];
typedef struct List{
    char str[15];
    friend bool operator<(List aa,List bb){
        return strlen(aa.str)<strlen(bb.str);
    }
}List;
List s[25];
bool vis[N];
int main(){
    ios::sync_with_stdio(false);
    int n,m;scanf("%d%d",&n,&m);
    cnt=0;root=csh();
    for(int i=1;i<=n;i++){
        scanf("%s",s[i].str);
    }
    for(int i=1;i<=n;i++) insert(s[i].str);
    for(int i=1;i<=m;i++){
        scanf(" %s",s1);
        int len=strlen(s1);
        memset(vis,0,sizeof(vis));int temp,j;
        for(int k=-1;k<len;k++){
                temp=root;
                if(k==-1||vis[k]==1){
                    if(k==-1) j=0;
                    else j=k+1;
                    while(j<len){
                        if(d[temp].a[s1[j]-'a']!=0) temp=d[temp].a[s1[j]-'a'];
                        else break;
                        //cout<<d[temp].sum<<endl;
                        if(d[temp].sum==1) vis[j]=1;
                        j++;
                    }
                }
            }
            int flag=0;
            for(int k=len-1;k>=0;k--){
                if(vis[k]){
                    printf("%d
",k+1);flag=1;break;
                }
            }
            if(flag==0) printf("0
");    
        }
    return 0;
}