P2292 [HNOI2004] L 语言 题解

· · 题解

Trie 树

(似乎没人发 Trie 树的题解，那我来一发

Solution

其实方法还是很好想的，就是将所有的单词丢进一棵 Trie 树里进行操作。

所以关键是如何对文本进行查询。

我们直接深搜，对每个位置查找下一位是否可以接上，如果扫完了一个单词，那么直接枚举从这个位置断开的方案。

实现也很简单。

如果接不上呢？那就 break。

还有每次都要更新 ans。

注：对于一个地方，如果已经搜过了那么没必要再搜一次因为可以接上的最大长度一定不会改变。

code：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6+10;

int n,q,ans;
char s[MAXN];
int vis[MAXN];
int cnt;
struct Trie{
    int son[26];
    int val;
}tr[1000];

void insert(){
    int now=0;
    int len=strlen(s);
    for(int i=0;i<len;++i){
        if(!tr[now].son[s[i]-'a']){
            tr[now].son[s[i]-'a']=++cnt;
        }
        now=tr[now].son[s[i]-'a'];
    }
    tr[now].val++;
}

void dfs(int pos,int len){
    if(vis[pos])
      return ;
    vis[pos]=1;
    int now=0;
    if(pos>ans)
      ans=pos;
    int x=pos;
    while(x<len){
        if(tr[now].son[s[x]-'a']){
            now=tr[now].son[s[x]-'a'];
            x++;
            if(tr[now].val)
              dfs(x,len);
        }
        else
          break;
    }
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;++i){
        scanf("%s",s);
        insert(); 
    }
    for(int i=1;i<=q;++i){
        memset(vis,0,sizeof(vis));
        ans=0; 
        scanf("%s",s);
        dfs(0,strlen(s));
        cout<<ans<<'\n';
    }
    return 0;
}

but，如果提交这份代码，你将获得一个至高无上的棕名！