2021.11.09 P2292 [HNOI2004]L语言（trie树+AC自动机）

https://www.luogu.com.cn/problem/P2292

题意：

标点符号的出现晚于文字的出现，所以以前的语言都是没有标点的。现在你要处理的就是一段没有标点的文章。

一段文章 TT 是由若干小写字母构成。一个单词 WW 也是由若干小写字母构成。一个字典 DD 是若干个单词的集合。我们称一段文章 TT 在某个字典 DD 下是可以被理解的，是指如果文章 TT 可以被分成若*分，且每一个部分都是字典 DD 中的单词。

例如字典 DD 中包括单词is,name,what,your则文章whatisyourname 是在字典 DD 下可以被理解的，因为它可以分成 44 个单词：what,is,your,name，且每个单词都属于字典 D，而文章 whatisyouname 在字典 D下不能被理解，但可以在字典 D' =D∪{you} 下被理解。这段文章的一个前缀whatis，也可以在字典 D下被理解，而且是在字典 D下能够被理解的最长的前缀。

给定一个字典 D，你的程序需要判断若干段文章在字典 D下是否能够被理解。并给出其在字典 D下能够被理解的最长前缀的位置。

分析：

模板。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define aa 2000010
int n,m;
char p[aa];
map<string,int>a;
map<string,int>b;
struct trie{
	int ch[aa][30],vis[aa],cnt,flag[aa];
	inline void clear(){
		memset(ch,0,sizeof(ch));
		memset(vis,0,sizeof(vis));
		cnt=0;
	}
	inline void insert(char *s){
		int u=0,l=strlen(s+1);
		//len=max(len,l);
		for(int i=1;i<=l;i++){
			int si=s[i]-'a';
			if(ch[u][si]==0){
				++cnt;
				ch[u][si]=cnt;
			}
			u=ch[u][si];
		}
		flag[u]=1;
	}
	/*inline bool find(int start,int end){
		int u=0;
		for(int i=start;i<=end;i++){
			int si=p[i]-'a';
			if(ch[u][si]==0)return 0;
			u=ch[u][si];
		}
		return vis[u];
	}*/
	inline int find(char *s){
		int u=0,l=strlen(s+1);
		if(a[s+1])return b[s+1];
		memset(vis,0,sizeof(vis));
		vis[0]=1;
		for(int i=0;i<=l;i++){
			if(vis[i]==0)continue;
			cnt=i;
			for(int j=i+1;j<=l;j++){
				int si=s[j]-'a';
				u=ch[u][si];
				if(u==0)break;
				if(flag[u])vis[j]=1;
			}
		}
		a[s+1]=1;b[s+1]=cnt;
		return cnt;
	}
}t;
inline int read(){
	int s=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s;
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		scanf("%s",p+1);
		t.insert(p); 
	}
	for(int i=1;i<=m;i++){
		scanf("%s",p+1);
		/*memset(f,0,sizeof(f));
		int l=strlen(p),ans=0;
		for(int j=0;j<l;j++){
			for(int k=max(j-len,-1);k<=j;k++){
				if((k==-1||f[k])&&t.find(k+1,j) ){
					f[j]=1;ans=j+1;
					break;
				}
			}
		}
		cout<<ans<<endl;*/
		cout<<t.find(p)<<endl; 
	}
	return 0;
}