学步园

后缀自动机在trie数基础上，引入了父节点parent,前缀nxt,后续child[],匹配单词数量cnt，其中child[i]为当前字符串遇到char i时跳转到的节点。
以下内容可以用bfs由浅入深初始化自动机。这个过程类似kmp，我觉得不同在于kmp不保存每一个节点遇到任意字母后跳转位置，而只保存它与前缀串(nxt)匹配位置
如下：
注意n#parent已经初始化完成。

if n#parent!=root(即n#parent#nxt!=n#parent)

             n#nxt=node[n#parent#nxt].child[n#idx]

if n#child[i]==null

             n#child[i]=node[n#nxt]->child[i]

n#cnt+=node[n#nxt].cnt

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
#define MAXLEN 1100000
#define CHILDCNT 26
using namespace std;
struct Node{
	int idx;
	int nxt;
	int pnt;
	int child[CHILDCNT];
	int cnt;// words matched
	void init(int parent,int childIdx){
		idx=childIdx;
		nxt=0,pnt=parent,cnt=0;
		memset(child,0,sizeof(child));
	}
};

struct TrieG{
	//int root=0;
	Node nodes[MAXLEN];
	int lst;
	TrieG(){
		lst=0;
		nodes[lst++].init(0,0);
	}
	string print(int i){
		if(i==0) return "";
		Node &n=nodes[i];
		char c='a'+n.idx;
		return print(n.pnt)+c;
	}
	void add(char* s){
		int v=0;
		int len=strlen(s);
		for(int i=0;i<len;i++){
			int of=s[i]-'a';
			if(!nodes[v].child[of]){
				nodes[v].child[of]=lst;
				nodes[lst].init(v,of);
				lst++;
			}
			v=nodes[v].child[of];
			if(i==len-1) nodes[v].cnt++;
		}
	}
	int init(){
		// nxt[0]=0,nxt[nodes[0].child[]]=0
		queue<int>que;
		que.push(0);
		while(!que.empty()){
			int v=que.front();que.pop();
			Node &n=nodes[v];
			for(int i=0;i<CHILDCNT;i++){
				if(n.child[i])
					que.push(n.child[i]);
			}
			if(v>0) {
				if(n.pnt>0) n.nxt=nodes[nodes[n.pnt].nxt].child[n.idx];
				n.cnt+=nodes[n.nxt].cnt;
				for(int i=0;i<CHILDCNT;i++){
				    if(!n.child[i])
					n.child[i]=nodes[n.nxt].child[i];
					// cout<<"v["<<v<<"]:"<<print(v)<<"->child["<<char('a'+i)<<"]:"<<n.child[i]<<endl;
				}
			}
		}
	}
	bool match(char *s){
		int len=strlen(s);
		int v=0;
		int count=0;
		for(int i=0;i<len;i++){
			v=nodes[v].child[s[i]-'a'];
			if(nodes[v].cnt) return true;
		}
		return false;
	}
};
int main(){
	TrieG g;
	// char *s[11]={"abcd","bcd","cd","d","abce","abef","abcdefg","a","ab","abc","abcd"};
	int n;cin>>n;
	char buf[1000001];
	for(int i=0;i<n;i++){
		cin>>buf; 
		g.add(buf);
	}
	g.init();
	cin>>buf;
	bool res=g.match(buf); 
	if(res) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}