菜鸡一个。

题解 P2292 【[HNOI2004]L语言】

2020-02-04 23:28:34


前往我的博客,食用效果更佳:链接

前置芝士:$Trie$字典树

这道题,说是AC自动机,实际上一个$Trie+$队列轻松搞定。

首先,我们对所有单词建一棵$Trie$。

然后,定义一个空队列$Q$,初始时把$-1$放进去(因为字符串下标从$0$开始,待会儿详细叙述原因)。

接着,对于每一篇询问的文章$T$,进行如下操作:

  1. 取出队头元素,假设是$x$。
  2. 更新$ans=\max(ans,x)$。
  3. 从$T[x+1]$开始枚举,进行$Trie$上的匹配。(这也解释了为什么刚开始要把$-1$放进去,因为这样才能从$0$开始枚举)
  4. 如果成功匹配$T[i]$,继续枚举,直到第$5$步被执行或者$i\ge T.length$。
  5. 否则,如果发现匹配不了了,立即退出循环,跳回第$1$步。
  6. 如果成功匹配$T[i]$,并且发现这里有字符串结尾标记,则说明成功匹配了一个单词,把$i$放进队尾。(注意:此时不能立即退出,待会儿讲原因)
  7. 执行$1-6$步,直到队列为空。

说明一下第$6$步,此时为什么不能直接退出呢?

比如:词典为$\{what,whatis\}$,文章为$whatisbalabala$。

如果直接退出,则匹配到$i=3$时就退出了,最后输出答案为$4$。(而实际为$6$)

这样,就可以开心地$code$啦:(看完代码不要心急,继续往下看)

#include <bits/stdc++.h>
using namespace std;
int n,m,trie[1000005][26],tot,c[1000005];
char tmp[1000005];
queue<int> q;
inline void addstring(char a[]){//添加字符串
    int len=strlen(a),pos=0;
    for(int i=0;i<len;i++){
        if(!trie[pos][a[i]-'a']){
            trie[pos][a[i]-'a']=++tot;
            pos=trie[pos][a[i]-'a'];
        }
        else pos=trie[pos][a[i]-'a'];
    }
    c[pos]=true;
}
inline int find(char a[]){
    memset(flag,0,sizeof(flag));
    int len=strlen(a),pos=0,ans=-1;q.push(-1);
    while(!q.empty()){
        int x=q.front();q.pop();//步骤1
        ans=max(ans,x);pos=0;//步骤2
        for(int i=x+1;i<len;i++){//步骤3
            if(trie[pos][a[i]-'a']) pos=trie[pos][a[i]-'a'];//步骤4
            else break;//步骤5
            if(c[pos]) q.push(i);//步骤6
        }
    }
    return ans==-1?0:ans+1;//字符串下标以0开始,而题目中以1开始
}
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++){
        scanf("%s",tmp);addstring(tmp);
    }
    for(register int i=1;i<=m;i++){
        scanf("%s",tmp);printf("%d\n",find(tmp));
    }
    return 0;
}

开心的交上去,咦?怎么只有$73pts$?

经不懈思考,终于构造出能卡掉的数据:

字典:$\{a,aa,aaa,...,aaaaaaaaaa\}$

文章:$\underbrace {aaa...aaa}_{10^6个a}$

于是,对于几乎每个位置$x$,都被插入队列至少$10$次,速度也就呵呵了......

那么,如何防止一个位置被重复插入?很简单,做个标记就行了。

改进后的代码:$(AC)$

#include <bits/stdc++.h>
using namespace std;
int n,m,trie[1000005][26],tot,c[1000005],flag[1000005];//flag即为标记数组
char tmp[1000005];
queue<int> q;
inline void addstring(char a[]){
    int len=strlen(a),pos=0;
    for(int i=0;i<len;i++){
        if(!trie[pos][a[i]-'a']){
            trie[pos][a[i]-'a']=++tot;
            pos=trie[pos][a[i]-'a'];
        }
        else pos=trie[pos][a[i]-'a'];
    }
    c[pos]=true;
}
inline int find(char a[]){
    memset(flag,0,sizeof(flag));//初始化标记数组
    int len=strlen(a),pos=0,ans=-1;q.push(-1);
    while(!q.empty()){
        int x=q.front();q.pop();
        ans=max(ans,x);pos=0;
        if(flag[x]) continue;//判断一下该位置是否已经有标记了,如果有就continue
        if(x!=-1) flag[x]=1;//否则做个标记
        for(int i=x+1;i<len;i++){
            if(trie[pos][a[i]-'a']) pos=trie[pos][a[i]-'a'];
            else break;
            if(c[pos]) q.push(i);
        }
    }
    return ans==-1?0:ans+1;
}
int main(){
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;i++){
        scanf("%s",tmp);addstring(tmp);
    }
    for(register int i=1;i<=m;i++){
        scanf("%s",tmp);printf("%d\n",find(tmp));
    }
    return 0;
}//开心的结束

最后,蒟蒻写博客不易,恳请大佬点个赞!