[HNOI2004]L语言字典树记忆化搜索

给出\(n\)个字符串作为字典，询问\(m\)个字符串，求每个字符串最远能匹配（字典中的字符串）到的位置

容易想到使用字典树维护字典，然后又发现不能每步一直贪心无脑取最长匹配，所以考虑\(dfs\)穷举情况，每次匹配到新字符串后，分两种情况，要么继续当前的匹配，要么完成当前匹配，开始进行下一个字符串的匹配。

但是这样显然会\(TLE\)，于是考虑记忆化，注意到性质：对于一个当前搜到并且之前已经搜过的位置，这个位置上的答案与前面如何搜的无关，于是记忆化，标记当前是否搜过，如果搜过就不搜了，因为反正都一样。

AC Code:

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

struct nod{

    bool hav;

    int nxt[26];

}t[1000005];

int tot;

inline void add(string s){

    int len=s.size(),rot=0;

    for(int i=0;i<len;++i){

        int cur=s[i]-'a';

        if(t[rot].nxt[cur]!=0){

            rot=t[rot].nxt[cur];

        }else{

            t[rot].nxt[cur]=++tot;

            rot=tot;

        }

    }

    t[rot].hav=1;

}

string s;

int len,ans;

bool hav[1000005];

void dfs(int pos){

	if(pos>=len) return;

	if(ans==len) return;

	int rot=0;

    for(int i=pos;i<len;++i){

        int cur=s[i]-'a';

        if(t[rot].nxt[cur]!=0){

            rot=t[rot].nxt[cur];

            if(t[rot].hav){

                ans=max(ans, i+1);

                pos=i+1;

                if(!hav[i]){

					dfs(i+1);

					hav[i]=1;

				}

            }

        }else{

        	ans=max(ans, pos);

            return;

        }

    }

}

int n,m;

int main(){

	ios::sync_with_stdio(0);

    cin>>n>>m;

    for(int i=1;i<=n;++i){

    	cin>>s;

    	add(s);

	}

    for(int i=1;i<=m;++i){

    	memset(hav, 0, sizeof(hav));

    	ans=0;

    	cin>>s;

    	len=s.size();

    	dfs(0);

    	cout<<ans<<endl;

	}

    return 0;

}

巴特西

[HNOI2004]L语言字典树记忆化搜索

[HNOI2004]L语言字典树记忆化搜索

最新文章

热门文章

巴特西

[HNOI2004]L语言 字典树 记忆化搜索

[HNOI2004]L语言 字典树 记忆化搜索

最新文章

热门文章

[HNOI2004]L语言字典树记忆化搜索

[HNOI2004]L语言字典树记忆化搜索