题解 P2292 【[HNOI2004]L语言】
Zesty_Fox
2020-02-04 23:28:34
前往我的博客，食用效果更佳：[链接](https://www.cnblogs.com/acceptedzhs/p/12262015.html)
前置芝士：$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$啦：（看完代码不要心急，继续往下看）
```cpp
#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)$
```cpp
#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;
}//开心的结束
```
最后，蒟蒻写博客不易，恳请大佬点个赞！