多模式串匹配算法

“天空无视了我的归途，于是我以梦为矛，贯穿星空。”

观前提醒

前置知识： 算法（字符串匹配算法）， 树（字典树）。

本笔记为复习笔记，以例题为主，讲解为辅。

更新日志

：起稿。

：写完 指针的构建部分。

：开始更新拓扑优化及二次加强版

：更新了一些例题

---

AC自动机

自动机，正式名字为多模式串匹配算法（）。

有一句话进行总结，就是在 树上进行 匹配，从而实现多个模式串的快速匹配，根据「字符串算法时间复杂度定理」（瞎说的），这个显然是 的。

首先，对于 树的构建是十分简单的，重点在于我们需要如何在 树建立失配指针。我们回顾 的过程，用一个函数 记为失配数组，对模式串进行自匹配，得到权值为如果当前位置不适配，那上一个可能适配位置的最大值（当前最大前后缀长度），由此，可以在最优的时间内进行字符串匹配，时间复杂度 ，其中 为模式串长度， 为匹配串长度。

在 自动机中，同样有一个失配函数 ，其中 ，当且仅当 是 的最长后缀，这个地方是与 最大的区别所在，一个是记录最长后缀长度，一个记录的是 。

什么是Border？

出现在早期 以及一些不可做级别的字符串题中，一个长度为 字符串 的 ，被钦定为一个权值 ，是满足 的最大的值 ，其中 。

例如对于以下字符串，我们记其 为 ，则：

$$\begin{align} f(\text{aaba})&=\nonumber 1=\text{a}\\ f(\text{aabaa})&=\nonumber 2=\text{aa}\\ f(\text{aabaaf})&=\nonumber 0=\varnothing\\ f(\text{abacefgsabac})&=\nonumber 4=\text{abac} \end{align}$$

这就是 算法中的前缀表。

建树/构造失配指针

类比于 ，重点在于如何构建 指针和如何使用 指针进行快速多模式串匹配。对于 ，我们依照字典树的深度顺序进行递推计算。记录 表示结点 与结点 之间使用字符 进行连接。

现在要求 ，那么当前对于所有深度小于 结点的 ， 都是已知的，记录 表示 的父结点：

1. 如果 存在，则 。
2. 如果 不存在，则查找 是否存在，回溯到操作 。
3. 直到根结点，则 。

据此操作，可以得到整棵 树的 值。在 上有一个极其直观的图像解释，不理解或者感兴趣的读者可以去看一看。

在某种层面上， 是支持动态修改查询的，因此，我们可以在每一次将某一个字符串插入 树的时候处理好这根字符链的 指针。而要求 指针是按顺序处理的，所以我们需要 建树而不是 。同时，这一种做法其实是在所有字符串读入完毕，也就是 已经成型之后再进行 指针的处理。

容易发现，如果按照我们刚刚提及的那种情况进行 指针处理，这个方法并不是线性的，甚至很可能强制为 的（也就是每一次都返回至 的情况）。所以我们考虑优化寻找 指针的做法，并引入我们此行的关键知识——自动机。

字典树与字典图

树就是字典树，但我们并不满于此，我们现在需要的是一个更加扩展的能够支持我们 进行多模式串匹配的图，也就是字典图。

我们考虑 树的基本特征，每一个结点 都存储了一个字符 ，记为 ，而从根结点到 这段路径的所有字符拼接而成，会得到某一个插入进 树的字符串的前缀（我们暂且记为 ）。但容易发现，我们从 向下继续深入时，可能并不能遍历到曾经插入 时所经历的字符串，但 的后缀可能会成为另一个字符串的前缀，也就是通过 指针进行遍历的中途意折，从而不必要回溯至 进行重新检索，以保证复杂度。而上述说法的实际操作，就是把 指向 。我们舍弃 的一部分前缀并直接从中间部分进行对另一个模式串的匹配，而当前模式串因为已经不存在后续部分了所以可以直接放弃检索，最终，我们只需要找到所有 的位置和个数即可。

这意味着我们在 树中新添加了一些「返祖边」，让 能够正常工作，并保证了时间复杂度在 之内，构造除了字典图，此时的字典图是一个有向图。

实现

的实现分为三个步骤，其一，插入 树，和 进行字符串查询的工作是一样；其二，构造自动机，也就是求解 指针；其三，查询。

插入

因为 指针在构造自动机的时候才会被使用，所以这个插入和 树的插入是一样的。

参考实现

inline void insert(char *s)
{
  int u=0;
  for(int i=1;s[i];++i)
  {
    if(!Tr[u].to[s[i]-'a']) Tr[u].to[s[i]-'a']=++Idx;
    u=Tr[u].to[s[i]-'a'];
  }
  ++Tr[u].cnt;
}

构造自动机

按照上述方法进行计算即可。

参考实现

inline void build()
{
  std::queue<int>Q;
  for(int i=0;i<26;++i) if(Tr[0].to[i]) Q.push(Tr[0].to[i]);
  while(!Q.empty())
  {
    int u=Q.front();Q.pop();
    for(int i=0,v;i<26;++i)
    {
      if((v=Tr[u].to[i])) Tr[v].fail=Tr[Tr[u].fail].to[i],Q.push(v);
      else Tr[u].to[i]=Tr[Tr[u].fail].to[i];
    }
  }	
}

查询

我们在整个 树上遍历模式串，每当走到一个结点的时候，沿着其 指针走直到上一个走过的地方或者根结点，并统计沿路的答案，这样可以保证不重不漏，且每一个结点至多会被走到一次，所以时间复杂度为 的。

总而言之，如果要求某一个结点对整体答案的贡献（也就是匹配到某一结点是能匹配的模式串权值），就求 树的路径和；如果要求某一个结点被匹配的次数，就求 树的子树和。

titie:参考实现

inline int query(char *s)
{
  int u=0,res=0;
  for(int i=1;s[i];++i)
  {
    u=Tr[u].to[s[i]-'a'];
    for(int v=u;v&&Tr[v].cnt!=-1;v=Tr[v].fail) res+=Tr[v].cnt,Tr[v].cnt=-1;
  }
  return res;
}

---

失配树与拓扑优化

我们试图解决下面这个问题。请在阅读了「例题/模式串的分别计算」后进行阅读本部分。

题目简介

题目名称： 自动机（二次加强版）

题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P5357

形式化题意：求每一个模式串在匹配串中出现的次数。

数据范围：

这个题可以直接使用例题，也就是加强版中的那个方法进行解决，我们对每一个 分别进行 ，因为不能进行判重，所以跳 指针时最坏情况下每一次只会跳 层，时间复杂度会退化到 。甚至常数比暴力略大。

这个时候，我们就需要用到 树的一些性质。

失配树

容易发现，除了根结点之外的所有结点，有且仅有一个失配参数，也就是 与 是一一对应的。如果我们把二元组 视作边，就会得到一棵以 树根结点为根的树，学术界称之为失配树（）。

而 就是 的父结点。

当字符串 被遍历到，也就是匹配成功了，那么作为 的所有后缀也会被匹配成功，尽管他们可能并不是一个模式串，也就意味着我们需要把 都给 一遍。

而实际上，执行这个操作只需要我们将 树进行子树求和即可，这样能够保证线性的时间复杂度。因此，在处理了 指针与每一个结点被经历的次数之后，进行子树求和即可得到每一个结点实际被匹配的次数了。

AC Code

// ----- Eternally question-----
// Problem: P5357 【模板】AC 自动机（二次加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5357
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-04 08:49:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10,MAXM=2e6+10;
int N,Mp[MAXN],Cnt[MAXM],ans[MAXM];
char Str[MAXM];
struct ACAM
{
	int Tr[MAXM][26],Fail[MAXM];
	int Idx;
	struct FailTree
	{
		struct G
		{ int next,to; }Edge[MAXM<<1];
		int Head[MAXM],Total;
		inline void addEdge(int u,int v)
		{
			Edge[++Total]=(G){Head[u],v};Head[u]=Total;
			Edge[++Total]=(G){Head[v],u};Head[v]=Total;
		}
		void dfsTree(int x,int last)
		{
			ans[x]=Cnt[x];
			for(int e=Head[x],v;e;e=Edge[e].next)
			{
				if((v=Edge[e].to)==last) continue;
				dfsTree(v,x);
				ans[x]+=ans[v];
			}
		}
	}Qry;
	inline void insert(char *s,int id)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u][s[i]-'a']) Tr[u][s[i]-'a']=++Idx;
			u=Tr[u][s[i]-'a'];
		}
		Mp[id]=u;
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<26;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0,v;i<26;++i)
			{
				if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
				else Fail[Tr[u][i]]=Tr[Fail[u]][i],Q.push(v);
			}
		}
	}
	inline void query(char *t)
	{
		int u=0;
		for(int i=1;t[i];++i)
		{
			u=Tr[u][t[i]-'a'];
			++Cnt[u];
		}
		for(int i=1;i<=Idx;++i) Qry.addEdge(i,Fail[i]);
		Qry.dfsTree(0,-1);
	}
	inline void print()
	{ for(int i=1;i<=N;++i,puts("")) write(ans[Mp[i]]); }
}Acam;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Acam.insert(Str,i);
	Acam.build();
	scanf("%s",Str+1);
	Acam.query(Str);
	Acam.print();
	return 0;
}
/*

*/

---

关于字典图，最经典的解释就是 树 树组成的有向无穷图，所谓有向，就是指 ，所谓无穷，就是按照每一个结点一定有出度。

而 树，也就是失配树，其实一般而言是由 扩展而来的，一般用于解决有关 的问题，如：

题目简介

题目名称：失配树
题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P5829

形式化题意：给定一个字符串 ，一共 次询问，每一次询问前缀 的最长公共 长度。

数据范围：

刚开始直接 std::min(Fail[p],Fail[q])，这样是不正确的，因为 的传递性并非是差分，例如：

字符串 拥有一个长度为 的 为 aab，却不存在长度为 的 。

我们记录 为 的最长 ，则 的 集合应该是：

$$\{f(s),f(f(s)),f(f(f(s))),\dots\}$$

这才是 的传递性，与树型结构类似，所以就衍生出了 。

AC Code

// ----- Eternally question-----
// Problem: P5829 【模板】失配树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5829
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-19 16:07:16
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e6+10;
char Str[MAXN];
int Q,Len,Fail[MAXN];
inline void build(char *s)
{
	Len=std::strlen(s+1);
	for(int i=2,j=0;i<=Len;++i)
	{
		while(j&&s[i]!=s[j+1]) j=Fail[j];
		if(s[i]==s[j+1]) ++j;
		Fail[i]=j;
	}
}
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total=1;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Siz[MAXN],Dep[MAXN],Fa[MAXN],Son[MAXN];
void dfsTree(int x,int last)
{
    Fa[x]=last,Siz[x]=1,Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x);
        Siz[x]+=Siz[v];
        if(!Son[x]||Siz[Son[x]]<Siz[v]) Son[x]=v;
    }
}
int Top[MAXN];
void dfsChain(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsChain(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
        dfsChain(v,v);
    }
}
inline int getLca(int x,int y)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		x=Fa[Top[x]];
	}
	return Dep[x]>Dep[y]?y:x;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	scanf("%s",Str+1);
	build(Str);
	for(int i=1;i<=Len;++i) addEdge(i,Fail[i]);
	dfsTree(0,Len+1),dfsChain(0,0);
	read(Q);
	for(int p,q;Q--;)
	{
		read(p,q);
		write(getLca(Fail[p],Fail[q]),'\n');
	}
	return 0;
}
/*

*/

---

例题

模式串的分别计算

题目简介

题目名称： 自动机（加强版）

题目来源：洛谷
评测链接：https://www.luogu.com.cn/problem/P3796

形式化题意：求出哪一个模式串在匹配串中出现次数最多以及出现的次数。

数据范围：

考虑与普通的 不同的地方，我们要对不同模式串进行不同的计算，也就是通过我们记录的每一个模式串的 分开记录。

AC Code

// ----- Eternally question-----
// Problem: P3796 【模板】AC 自动机（加强版）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3796
// Memory Limit: 128 MB
// Time Limit: 3000 ms
// Written by: Eternity
// Time: 2023-05-01 09:53:48
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=160,MAXM=80,MAXS=1e6+10;
int N;
char Cmp[MAXN][MAXM],Str[MAXS];
int Cnt[MAXN],Id[MAXS];
struct ACAM
{
	int Idx;
	struct Trie
	{ int to[26],fail,cnt; }Tr[MAXS];
	inline void init()
	{
		for(int i=0;i<=Idx;++i)
		{
			Tr[i].fail=Tr[i].cnt=0;
			for(int v=0;v<26;++v) Tr[i].to[v]=0;
		}
		Idx=0;
		std::memset(Cnt,0,sizeof(Cnt));
		std::memset(Id,0,sizeof(Id));
	}
	inline void insert(char *s,int id)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u].to[s[i]-'a']) Tr[u].to[s[i]-'a']=++Idx;
			u=Tr[u].to[s[i]-'a'];
		}
		Id[u]=id;
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<26;++i) if(Tr[0].to[i]) Q.push(Tr[0].to[i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0;i<26;++i)
				if(Tr[u].to[i]) Tr[Tr[u].to[i]].fail=Tr[Tr[u].fail].to[i],Q.push(Tr[u].to[i]);
				else Tr[u].to[i]=Tr[Tr[u].fail].to[i];
		}
	}
	inline int query(char *s)
	{
		int u=0,res=0;
		for(int i=1;s[i];++i)
		{
			u=Tr[u].to[s[i]-'a'];
			for(int v=u;v;v=Tr[v].fail) ++Tr[v].cnt;
		}
		for(int i=0;i<=Idx;++i) if(Id[i])
			checkMax(res,Tr[i].cnt),Cnt[Id[i]]=Tr[i].cnt;
		return res;
	}
}Acam;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	while(true)
	{
		read(N);
		if(!N) break;
		Acam.init();
		for(int i=1;i<=N;++i) scanf("%s",Cmp[i]+1),Acam.insert(Cmp[i],i);
		Acam.build();
		scanf("%s",Str+1);
		int ans=Acam.query(Str);
		write(ans,'\n');
		for(int i=1;i<=N;++i) if(Cnt[i]==ans) write(Cmp[i]+1,'\n');
	}
	return 0;
}
/*

*/

---

模式串逆匹配

题目简介

题目名称：病毒
题目来源：

评测链接：https://www.luogu.com.cn/problem/P2444

形式化题意：给定一些长度不一的 串 ，求是否存在一个长度为无穷的 串 使得没有一个 是 的子串。

数据范围：

如果我们将 建成一棵 树，且当前已经知道了 ，那么我们需要保证 在遍历 树时不会经历任何一个 。也就是 树所建成的字典图中存在一个不包含任意 结点的环。于是我们按照 的方法进行遍历即可。

titie:AC Code

// ----- Eternally question-----
// Problem: P2444 [POI2000]病毒
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2444
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-03 08:18:20
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e3+10,MAXM=3e4+10;
int N;
char Str[MAXM];
struct ACAM
{
	int Idx,End[MAXM];
	bool Ins[MAXM],Vis[MAXM];
	struct Trie
	{ int to[2],fail; }Tr[MAXM];
	inline void insert(char *s)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u].to[s[i]-'0']) Tr[u].to[s[i]-'0']=++Idx;
			u=Tr[u].to[s[i]-'0'];
		}
		End[u]=1;
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<2;++i) if(Tr[0].to[i]) Q.push(Tr[0].to[i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0,v;i<2;++i)
			{
				if(!(v=Tr[u].to[i])) Tr[u].to[i]=Tr[Tr[u].fail].to[i];
				else Tr[v].fail=Tr[Tr[u].fail].to[i],End[v]|=End[Tr[Tr[u].fail].to[i]],Q.push(v);
			}
		}
	}
	void search(int u)
	{
		if(Ins[u]){ puts("TAK");exit(0); }
		if(Vis[u]||End[u]) return ;
		Vis[u]=Ins[u]=1;
		for(int i=0;i<2;++i) search(Tr[u].to[i]);
		Ins[u]=0;
	}
}Tr;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Tr.insert(Str);
	Tr.build(),Tr.search(0);
	puts("NIE");
	return 0;
}
/*

*/

---

多模式匹配与动态规划

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P3041

形式化题意：给定 个由 A,B,C 组成的字符串 ，求一个长度为 的字符串 使得 在 中出现次数最多。问最多能出现多少次。

数据范围：

容易想到应该是使用 来解决。设置 表示长度为 ，最后一个字母为 的状态，但这样存在后效性，所以可能需要记录更多的后位，变成 表示后 位的状态，变成 的时间复杂度，这样对状态的限制很大，所以不考虑这样做。

容易发现类似于多模式串匹配，可以用 自动机做一些优化。做 树 。用 表示在 树编号为 的结点上，此时 串长度为 时的最大答案。此时可以直接转移：

$$dp[v,k]=\max\Big(dp[v,k],dp[u,k-1]+cnt(v)\Big)$$

注意 要进行 和处理，因为当遍历到一个结点 时，如果 存在匹配，肯定也会匹配成功，所以需要计算多次答案。

titie:AC Code

// ----- Eternally question-----
// Problem: P3041 [USACO12JAN]Video Game G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3041
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-04 11:29:42
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=22,MAXS=20,MAXK=1e3+10;
const int INF=0x3f3f3f3f;
int N,K;
char Str[MAXS];
struct ACAM
{
	int Idx;
	int Tr[MAXK][3],Fail[MAXK],Cnt[MAXK];
	int Dp[MAXK][MAXK];
	inline void insert(char *s)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u][s[i]-'A']) Tr[u][s[i]-'A']=++Idx;
			u=Tr[u][s[i]-'A'];
		}
		++Cnt[u];
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<3;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0,v;i<3;++i)
			{
				if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
				else Fail[v]=Tr[Fail[u]][i],Q.push(v);
			}
			Cnt[u]+=Cnt[Fail[u]];
		}
	}
	inline void query()
	{
		std::memset(Dp,-0x3f,sizeof(Dp));
		for(int i=0;i<=K;++i) Dp[0][i]=0;
		for(int len=1;len<=K;++len)
			for(int u=0;u<=Idx;++u)
				for(int i=0;i<3;++i)
					checkMax(Dp[Tr[u][i]][len],Dp[u][len-1]+Cnt[Tr[u][i]]);
		int ans=-INF;
		for(int u=0;u<=Idx;++u) checkMax(ans,Dp[u][K]);
		write(ans);
		return ;
	}
}Acam;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,K);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Acam.insert(Str);
	Acam.build();
	Acam.query();
	return 0;
}
/*

*/

---

多模式匹配与动态规划II

titie:题目简介

题目名称：文本生成器
题目来源：江苏省选

评测链接：https://www.luogu.com.cn/problem/P4052

形式化题意：给定了 个模式串，求字符集为 ，长度为 的字符串中，至少出现过 个模式串的匹配串的个数，对 取模。

数据范围：

令 表示不存在任何子串为 的字符串的个数，则答案为 ，考虑逆向思考。同样使用 自动机加上 来解决，设 表示答案计数，则转移可以为：

$$dp[Tr[u,c],len]=\sum dp[u,len-1]$$

当然，我们要保证 不被匹配，就可以进行转移了。最后答案为 。

正向也是可以做的，容斥一下就行了。（不保证复杂度能过）

AC Code

// ----- Eternally question-----
// Problem: P4052 [JSOI2007]文本生成器
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4052
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-04 16:56:57
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=6e3+10,MAXM=1e2+10;
const int Mod=1e4+7;
template<class T>
inline void add(T &x,T y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M;
char Str[MAXM];
inline int qPow(int a,int b)
{
	int res=1;
	for(;b;b>>=1,a=(ll)a*a%Mod) (b&1)&&(res=(ll)res*a%Mod);
	return res;
}
struct ACAM
{
	int Tr[MAXN][26],Fail[MAXN],Idx;
	bool Mk[MAXN];
	int Dp[MAXM][MAXN];
	inline void insert(char *s)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u][s[i]-'A']) Tr[u][s[i]-'A']=++Idx;
			u=Tr[u][s[i]-'A'];
		}
		Mk[u]=1;
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<26;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0,v;i<26;++i)
			{
				if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
				else Fail[v]=Tr[Fail[u]][i],Q.push(v),Mk[v]|=Mk[Fail[v]];
			}
		}
	}
	inline void dp()
	{
		Dp[0][0]=1;
		for(int len=1;len<=M;++len) for(int u=0;u<=Idx;++u)
			for(int c=0;c<26;++c) if(!Mk[Tr[u][c]])
				add(Dp[len][Tr[u][c]],Dp[len-1][u]);
		int delta=0;
		for(int u=0;u<=Idx;++u) add(delta,Dp[M][u]);
		write(((qPow(26,M)-delta)%Mod+Mod)%Mod);
	}
}Acam;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Acam.insert(Str);
	Acam.build(),Acam.dp();
	return 0;
}
/*

*/

---

多模式匹配与树论

题目简介

题目名称：

题目来源：

评测链接 ：https://loj.ac/p/3733
评测链接 ：https://www.luogu.com.cn/problem/P5840

形式化题意：给定 个字符串 ，以及一个字符串集合 ，初始时 为空，会进行 次操作：

1. 向 中添加字符串 ；
2. 求 是 中多少个字符串的子串。

数据范围：

考虑应该是动态插入 树，所以对 串构造 自动机。每次插入 串求得其对答案的影响，最后统计的时候是一个 树子树求和的过程，需要动态维护，可以考虑差分套 ，也可以树剖直接维护。按理说一支 或者两支 都可以过。

AC Code

// ----- Eternally question-----
// Problem: P5840 [COCI2015]Divljak
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5840
// Memory Limit: 768 MB
// Time Limit: 4000 ms
// Written by: Eternity
// Time: 2023-05-06 15:39:03
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10,MAXS=2e6+10;
int N,Q,Id[MAXS];
char Str[MAXS];
struct G
{
	int next,to;
}Edge[MAXS<<1];
int Head[MAXS],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Fa[MAXS],Son[MAXS],Dep[MAXS],Siz[MAXS];
void dfsTree(int x,int last)
{
	Siz[x]=1,Fa[x]=last,Dep[x]=Dep[last]+1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==last) continue;
		dfsTree(v,x);
		Siz[x]+=Siz[v];
		if(!Son[x]||Siz[v]>Siz[Son[x]]) Son[x]=v;
	}
}
int Dfn[MAXS],Lst[MAXS],Rst[MAXS],Top[MAXS],Cnt;
void dfsChain(int x,int topf)
{
	Top[x]=topf,Dfn[x]=Lst[x]=++Cnt;
	if(Son[x]) dfsChain(Son[x],topf);
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if((v=Edge[e].to)==Fa[x]||v==Son[x]) continue;
		dfsChain(v,v);
	}
	Rst[x]=Cnt;
}
#define ls (p<<1)
#define rs (p<<1|1)
struct Segment
{ int l,r,val; }Tr[MAXS<<2];
inline void pushUp(int p)
{ Tr[p].val=Tr[ls].val+Tr[rs].val; }
void build(int p,int l,int r)
{
	Tr[p].l=l,Tr[p].r=r;
	if(l==r) return Tr[p].val=0,void();
	int mid=(l+r)>>1;
	build(ls,l,mid),build(rs,mid+1,r);
	pushUp(p);
}
void modifyX(int p,int x,int v)
{
	if(Tr[p].l==Tr[p].r) return Tr[p].val+=v,void();
	int mid=(Tr[p].l+Tr[p].r)>>1;
	x<=mid?modifyX(ls,x,v):modifyX(rs,x,v);
	pushUp(p);
}
int querySum(int p,int l,int r)
{
	if(l>r) return 0;
	if(l<=Tr[p].l&&Tr[p].r<=r) return Tr[p].val;
	int mid=(Tr[p].l+Tr[p].r)>>1,res=0;
	if(l<=mid) res+=querySum(ls,l,r);
	if(mid<r) res+=querySum(rs,l,r);
	return res;
}
inline int getLca(int x,int y)
{
	while(Top[x]!=Top[y])
	{
		if(Dep[Top[x]]<Dep[Top[y]]) std::swap(x,y);
		x=Fa[Top[x]];
	}
	return Dep[x]>Dep[y]?y:x;
}
inline bool cmp(int x,int y){ return Dfn[x]<Dfn[y]; }
struct ACAM
{
	int Tr[MAXS][26],Fail[26],Idx;
	inline void insert(char *s,int id)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u][s[i]-'a']) Tr[u][s[i]-'a']=++Idx;
			u=Tr[u][s[i]-'a'];
		}
		Id[id]=u;
	}
	inline void build()
	{
		std::queue<int>Q;
		for(int i=0;i<26;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
		while(!Q.empty())
		{
			int u=Q.front();Q.pop();
			for(int i=0,v;i<26;++i)
			{
				if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
				else Fail[v]=Tr[Fail[u]][i],Q.push(v);
			}
			addEdge(u,Fail[u]);
		}
	}
	int Base[MAXS];
	inline void lengthen(char *T)
	{
		int u=0,idx=0;
		for(int i=1;T[i];++i) u=Tr[u][T[i]-'a'],Base[++idx]=u;
		std::sort(Base+1,Base+idx+1,cmp);
		idx=std::unique(Base+1,Base+idx+1)-Base-1;
		for(int i=1;i<=idx;++i)
		{
			modifyX(1,Dfn[Base[i]],1);
			if(i!=1) modifyX(1,Dfn[getLca(Base[i],Base[i-1])],-1);
		}
	}
}Acam;
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Acam.insert(Str,i);
	Acam.build();
	dfsTree(0,-1),dfsChain(0,0);
	build(1,1,Cnt);
	read(Q);
	for(int opt;Q--;)
	{
		read(opt);
		if(opt==1)
		{
			scanf("%s",Str+1);
			Acam.lengthen(Str);
		}
		else
		{
			int qx;read(qx);
			int ans=querySum(1,1,Rst[Id[qx]])-querySum(1,1,Lst[Id[qx]]-1);
			write(ans,'\n');
		}
	}
	return 0;
}
/*

*/

---

多模式匹配和数位dp

题目简介

题目名称：数数
题目来源：山东省选

评测链接：https://www.luogu.com.cn/problem/P3311

形式化题意：给定 个数字串 ，求 中有多少个数不包含任意的 。对 取模。

数据范围：， 无前导 ， 可能有前导 。

考虑一个数位 的做法，但题目又有些类似于多模式串匹配，就考虑在数位 的过程中记录一个参数表示当前在 自动机上的结点编号，然后正常数位 即可。

AC Code

// ----- Eternally question-----
// Problem: P3311 [SDOI2014] 数数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3311
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-10 08:57:40
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1.2e3+10,MAXM=1.5e3+10;
const int Mod=1e9+7;
template<class T>
inline void add(T &x,T y){ x=x+y>=Mod?x+y-Mod:x+y; }
int N,M,Idx;
char Str[MAXM];
int Tr[MAXM][10],Fail[MAXM],End[MAXM];
inline void insert(char *s)
{
	int u=0;
	for(int i=1;s[i];++i)
	{
		if(!Tr[u][s[i]-'0']) Tr[u][s[i]-'0']=++Idx;
		u=Tr[u][s[i]-'0'];
	}
	End[u]|=1;
}
inline void build()
{
	std::queue<int>Q;
	for(int i=0;i<10;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=0,v;i<10;++i)
		{
			if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
			else Fail[v]=Tr[Fail[u]][i],Q.push(v);
		}
		End[u]|=End[Fail[u]];
	}
}
int Dp[MAXN][MAXM][2][2],Nums[MAXN],Cnt;
int Dfs(int pos,int u,bool limit,bool _0)
{
	if(!pos) return (!_0)&(!End[u]);
	if(End[u]) return 0;
	if(~Dp[pos][u][limit][_0]) return Dp[pos][u][limit][_0];
	int num=limit?Nums[pos]:9,res=0;
	for(int i=0;i<=num;++i) add(res,Dfs(pos-1,(_0&(!i))?0:Tr[u][i],limit&(i==Nums[pos]),_0&(!i)));
	return Dp[pos][u][limit][_0]=res;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1),read(M);
	Cnt=std::strlen(Str+1);
	std::reverse(Str+1,Str+Cnt+1);
	for(int i=1;i<=Cnt;++i) Nums[i]=Str[i]-'0';
	while(M--)
	{
		scanf("%s",Str+1);
		insert(Str);
	}
	build();
	std::memset(Dp,-1,sizeof(Dp));
	write(Dfs(Cnt,0,1,1));
	return 0;
}
/*

*/

---

多模式匹配与搜索

题目简介

题目名称：病毒检测
题目来源：安徽省选

评测链接：https://www.luogu.com.cn/problem/P2536

形式化题意：给定一个病毒串，由 A,C,G,T,?,* 组成，? 可以表示 A,C,G,T 中的任意一个，* 可以表示由 A,C,G,T 组成的任意一个字符串，给定 个 串，求有多少个 串不能由病毒串扩展而出。

数据范围：

依然是多模式串匹配的问题，还是选择建出 树，发现其实可以直接在 树上进行 或者 ，然后统计所有的 即可。

挺有意思一题， 的时候记得记忆化就是了。

AC Code

// ----- Eternally question-----
// Problem: P2536 [AHOI2005] 病毒检测
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2536
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-10 16:23:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=5e2+10,MAXM=1e3+10,MAXS=5e5+10;
char Modo[MAXM],Str[MAXN];
int N,Len;
std::bitset<1024>Vis[MAXS];
struct Trie
{
	int Tr[MAXS][5],Val[MAXS],Idx;
	inline int val(int i){ return Val[i]; }
	inline void clear(){ std::memset(Tr,0,sizeof(Tr)),Idx=0; }
	inline int id(char c)
	{
		switch(c)
		{
			case 'A':return 1;
			case 'G':return 2;
			case 'T':return 3;
			case 'C':return 4;
			case '?':return 5;
			case '*':return 6;
		}
		return 0;
	}
	inline void insert(char *s)
	{
		int u=0;
		for(int i=1;s[i];++i)
		{
			if(!Tr[u][id(s[i])]) Tr[u][id(s[i])]=++Idx;
			u=Tr[u][id(s[i])];
		}
		++Val[u];
	}
}Tr;
int ans=0;
void Dfs(int pos,int u)
{
	if(pos>Len)
	{
		ans+=Tr.val(u),Tr.Val[u]=0;
		return ;
	}
	if(Vis[u][pos]) return ;
	int x=Tr.id(Modo[pos]);
	Vis[u][pos]=1;
	if(1<=x&&x<=4) (!!Tr.Tr[u][x])&&(Dfs(pos+1,Tr.Tr[u][x]),1);
	else if(x==5)
	{
		for(int i=1;i<=4;++i) (!!Tr.Tr[u][i])&&(Dfs(pos+1,Tr.Tr[u][i]),1);
	}
	else if(x==6)
	{
		Dfs(pos+1,u);
		for(int i=1;i<=4;++i) (!!Tr.Tr[u][i])&&(Dfs(pos,Tr.Tr[u][i]),Dfs(pos+1,Tr.Tr[u][i]),1);
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Modo+1);
	Len=std::strlen(Modo+1);
	read(N);
	for(int i=1;i<=N;++i) scanf("%s",Str+1),Tr.insert(Str);
	Dfs(1,0);
	write(N-ans);
	return 0;
}
/*

*/

---

多模式匹配与动态规划III

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P3502

形式化题意：给定 个互不包含的字符串，求一个字符串 ，使得这 个字符串至少在 中出现 ，求最小的 。

数据范围：

考虑 状态，设 表示拼了 个串，最后一个串编号为 的最小长度。预处理出一个函数 表示在 后拼接多少个字符才能得到 ，显然地，这个可用 自动机来解决，由此写出转移方程：

$$dp[x,i]=\min\{dp[x-1,j]+dis(j,i)\}$$

得出一个 的做法，发现这个转移方程可以用广义矩乘加速，所以优化到 。

用 或者哈希加 之类的都可以过。

AC Code

// ----- Eternally question-----
// Problem: P3502 [POI2010]CHO-Hamsters
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3502
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-15 21:50:29
// ----- Endless solution-------

#include<bits/stdc++.h>
#define  register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *Str){ while(*Str!='\0') putchar(*Str++); }
template<>
inline void write(const char *Str){ while(*Str!='\0') putchar(*Str++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10;
const int MAXS=1e6+10;
ll N,M,Idx,ans=1ll<<60;
int End[MAXS],Id[MAXS],Len[MAXN],Fail[MAXS],Dep[MAXS];
int Tr[MAXS][26];
char Str[MAXS];
struct Matrix
{
	ll a[MAXN][MAXN];
	ll* operator[](int i){ return a[i]; }
	Matrix(){ std::memset(a,0x3f,sizeof(a)); }
	inline void idx(){for(int i=1;i<=N;++i)a[i][i]=1;}
}A;
Matrix operator*(Matrix &x,Matrix &y)
{
	Matrix res;￥
	for(int i=1;i<=N;++i)
		for(int j=1;j<=N;++j)
			for(int k=1;k<=N;k++)
				checkMin(res[i][j],x[i][k]+y[k][j]);
	return res;
}
Matrix operator ^(Matrix &a,ll k)
{
    Matrix res;
    for(int i=1;i<=N;++i) res[i][i]=0;
    while(k)
    {
        if(k&1)res=res*a;
        a=a*a;k>>=1;
    }
    return res;
}
inline void insert(char* s,int id)
{
	int Len=strlen(s+1),u=0;
	for(int i=1;i<=Len;++i)
	{
		int c=s[i]-'a';
		if(!Tr[u][c]) Tr[u][c]=++Idx;
		u=Tr[u][c];
	}
	End[u]=id;Id[id]=u;
}
inline void getFail()
{
	std::queue<int>Q;Q.push(0);
	while(!Q.empty())
	{
		int x=Q.front();Q.pop();
		for(int i=0;i<26;++i)
		{
			int y=Tr[x][i];
			if(!y) continue;
			int k=Fail[x];
			while(k&&(!Tr[k][i]))k=Fail[k];
			Fail[y]=x?Tr[k][i]:0;
			Q.push(y);
		}
	}
}
inline void build()
{
	for(int i=1;i<=N;++i)
		for(int j=Id[i];Fail[j];j=Fail[j])
		{
			Dep[Fail[j]]=0;
			std::queue<int>Q;Q.push(Fail[j]);
			while(!Q.empty())
			{
				int x=Q.front();Q.pop();
				for(int k=0;k<26;k++)
				{
					int y=Tr[x][k];
					if(!y)continue;
					A[i][End[y]]=Dep[y]=Dep[x]+1;Q.push(y);
				}
			}	
		}		
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	if(!M) return puts("0"),0;
	for(int i=1;i<=N;++i)
	{
		scanf("%s",Str+1);Len[i]=std::strlen(Str+1);
		insert(Str,i);
		for(int j=1;j<=N;++j) A[j][i]=Len[i];
	}
	getFail();build();
	A=A^(M-1);
	for(int i=1;i<=N;++i) for(int j=1;j<=N;++j) checkMin(ans,A[i][j]+Len[i]);
	printf("%lld",ans);
	return 0;
}
/*

*/

---

多模式匹配与数据结构

题目简介

题目名称：阿狸的打字机
题目来源：

评测链接：https://www.luogu.com.cn/problem/P2414

形式化题意：给定一个操作串包含小写字母以及 B,P，其中小写字母表示在当前生成的字符串后加入这个小写字母，B 表示删除最后一个字母，P 表示将当前这个字符串复制一份提出，记为第 个字符串 （此前有 次 P 操作），有 个询问，询问 在 中出现过几次。

数据范围：

对于预处理，可以考虑建一个 自动机存储，但如此的话，每一个询问都是 的。所以考虑统计 树上的路径和，考虑离线询问，在跑 树的时候用 维护 树的路径和，统计答案即可。

时间复杂度不超过一支 。

AC Code

// ----- Eternally question-----
// Problem: P2414 [NOI2011] 阿狸的打字机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2414
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-22 11:28:56
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
char Str[MAXN];
int N,Q,Idx,Nd[MAXN],ans[MAXN];
int Tre[MAXN],Dfn[MAXN],Low[MAXN],Tim;
int Ql[MAXN],Qr[MAXN];
inline int lowbit(int x){ return x&(-x); }
inline void add(int x,int v){ for(;x<=Tim;x+=lowbit(x)) Tre[x]+=v; }
inline int query(int x)
{
	int res=0;
	for(;x;x-=lowbit(x)) res+=Tre[x];
	return res;
}
struct ACAM
{
	int to[26],vis[26];
	int fail,fa,lt;
}Tr[MAXN];
struct Question{ int x,y,id,ans; }Qry[MAXN];
bool operator<(Question a,Question b){ return a.y<b.y; }
inline void build()
{
	std::queue<int>Q;
	for(int i=0;i<26;++i) if(Tr[0].to[i]) Q.push(Tr[0].to[i]);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=0,v;i<26;++i)
		{
			if(!(v=Tr[u].to[i])) Tr[u].to[i]=Tr[Tr[u].fail].to[i];
			else Tr[v].fail=Tr[Tr[u].fail].to[i],Q.push(v);
		}
	}
}
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
void Dfs(int x)
{
	Dfn[x]=++Tim;
	for(int e=Head[x];e;e=Edge[e].next) Dfs(Edge[e].to);
	Low[x]=Tim;
}
void dfsTree(int x)
{
	add(Dfn[x],1);
	if(Tr[x].lt) for(int i=Ql[Tr[x].lt];i<=Qr[Tr[x].lt];++i)
		Qry[i].ans=query(Low[Nd[Qry[i].x]])-query(Dfn[Nd[Qry[i].x]]-1);
	for(int i=0;i<26;++i) if(Tr[x].vis[i]) dfsTree(Tr[x].vis[i]);
	add(Dfn[x],-1);
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1);
	for(int i=1,l=std::strlen(Str+1),u=0;i<=l;++i)
	{
		if(Str[i]>='a'&&Str[i]<='z')
		{
			if(!Tr[u].to[Str[i]-'a']) Tr[u].to[Str[i]-'a']=++Idx,Tr[Idx].fa=u;
			u=Tr[u].to[Str[i]-'a'];
		}
		if(Str[i]=='B') u=Tr[u].fa;
		if(Str[i]=='P') Nd[++N]=u,Tr[u].lt=N;
	}
	for(int i=0;i<=Idx;++i) for(int c=0;c<26;++c) Tr[i].vis[c]=Tr[i].to[c];
	read(Q);
	build();
	for(int i=1;i<=Idx;++i) addEdge(Tr[i].fail,i);
	Dfs(0);
	for(int i=1;i<=Q;++i)
	{
		read(Qry[i].x,Qry[i].y);
		Qry[i].id=i;
	}
	std::sort(Qry+1,Qry+Q+1);
	for(int i=1,pos=1;i<=Q;i=pos)
	{
		Ql[Qry[i].y]=i;
		while(Qry[pos].y==Qry[i].y) ++pos;
		Qr[Qry[i].y]=pos-1;
	}
	dfsTree(0);
	for(int i=1;i<=Q;++i) ans[Qry[i].id]=Qry[i].ans;
	for(int i=1;i<=Q;++i) write(ans[i],'\n');
	return 0;
}
/*

*/

---

多模式匹配与数据结构II

题目简介

题目名称：

题目来源：

评测链接：https://www.luogu.com.cn/problem/P3121

形式化题意：给定一个文本串 ，以及 个匹配串 ，要求每一次在 中找到 并将其删除直到不存在任何 ，求最后的文本串。

数据范围：

首先建 自动机，每一次匹配就将该串删除即可。但注意到可能会删除到之前删除过的一部分，所以考虑用一个 std::stack 来存储答案串。

AC Code

// ----- Eternally question-----
// Problem: P3121 [USACO15FEB]Censoring G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3121
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-23 14:35:51
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int N;
char Str[MAXN],Mod[MAXN];
int Tr[MAXN][26],Fail[MAXN],Val[MAXN],Idx;
int Stk[MAXN],Loc[MAXN],Top;
inline void insert(char *s)
{
	int u=0;
	for(int i=1;s[i];++i)
	{
		if(!Tr[u][s[i]-'a']) Tr[u][s[i]-'a']=++Idx;
		u=Tr[u][s[i]-'a'];
	}
	Val[u]=std::strlen(s+1);
}
inline void build()
{
	std::queue<int>Q;
	for(int i=0;i<26;++i) if(Tr[0][i]) Q.push(Tr[0][i]);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=0,v;i<26;++i)
		{
			if(!(v=Tr[u][i])) Tr[u][i]=Tr[Fail[u]][i];
			else Fail[v]=Tr[Fail[u]][i],Q.push(v);
		}
	}
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	scanf("%s",Str+1),read(N);
	for(int i=1;i<=N;++i) scanf("%s",Mod+1),insert(Mod);
	build();
	for(int i=1,u=0,l=std::strlen(Str+1);i<=l;++i)
	{
		Loc[i]=u=Tr[u][Str[i]-'a'];
		Stk[++Top]=i;
		if(Val[u])
		{
			Top-=Val[u];
			u=Loc[Stk[Top]];
		}
	}
	for(int i=1;i<=Top;++i) putchar(Str[Stk[i]]);
	return 0;
}
/*

*/

---

确定有限状态自动机

自动机应当是 中学习到的第一个自动机。是一个确定有限状态自动机（，简称 ）。

一个 可以分为 个部分：

• 状态集合 ；
• 字符集 ；
• 状态转移函数 ，即 ；
• 初始状态 ；
• 接受状态集合 。

一个 就可以用一个五元组 表示了。

常见的自动机有 自动机， 自动机，后缀自动机等，都是字符串中常用的算法。

的主要作用是识别字符串，对于一个自动机 而言，如果能识别字符串 ，则 ，否则为 。类比于 自动机，当我们向一个自动机读入一个字符串 ，并依次转移，当读入转移过程结束后转移到的依然是一个接受状态，则称该 接受这个字符串，否则这个 不接受这个字符串。

如果状态 不存在 的转移，我们记 ，其中 。

我们对 进行广义定义，记为 ，其中 表示一个字符串，是由多个 中的字符构成的，也就是：

$$\delta(u,s)=\delta(\delta(u,s_1),s_{2\sim|s|})$$

显而易见的，有 。

后缀链接

定义一个状态（对应若干字符串）的后缀链接，是指该自动机上该状态中若干字符串的最长公共真后缀。一般而言，后缀链接会形成一个树型结构， 树就是 自动机的后缀链接树，不同的后缀链接树往往有相同的性质。

子序列自动机

子序列自动机（）是一个 ，仅接受字符串的子序列的自动机，用于高效处理子序列问题。

如果我们现在有一个字符串为 ，则其子序列自动机一共有 个状态，设定 为 的一个子序列，则 指向 在 第一次出现的末位置。用一句不太好理解的话理解就是（出自 ），一个状态 表示前缀 与 的子序列的差集。在序列自动机中 。

对于实现，我们依旧选择维护 ，即转移函数，其中 表示 之后第一个出现 位置，如果没有，则 。容易发现，这样我们可以通过转移函数到 结束的路径就是 的一个子序列。

为什么要选择第一个？

秉承一个贪心的想法，如果转移越往后，能够得到的子序列长度期望就越小，所以考虑选择第一个，因为如果字符集是一样的话，如何选择对于答案的计算是不变的，除非要统计个数，这个之后会提及。

---

构建子序列自动机

如果 较小，我们可以考虑类似于 自动机那样的暴力构建，直接维护 ，倒叙枚举 ，记录 表示字符 当前最靠前的位置，更新即可。

参考实现

int N,S;
//长度，字符集大小
inline void build(auto *s)
//这里不限于字符串，同样可以是一个数列
{
	for(int c=1;c<=S;++c) Pos[c]=N+1;
	for(int i=N;i;--i)
	{
		for(int c=1;c<=S;++c) Tr[i][c]=Pos[c];
		Pos[s[i]]=i;
	}
}

时间复杂度 ，空间复杂度同样。

我们接下来上上手。

titie:题目简介

题目名称：所有公共子序列问题 / 公共子序列 / 公共子串
题目来源：福建省选 / 导刊 / 天津省选

评测链接 ：https://www.luogu.com.cn/problem/P4608
评测链接 ：https://www.luogu.com.cn/problem/P1819
评测链接 ：https://www.luogu.com.cn/problem/P3856

形式化题意：给定 个字符串，求其公共子序列。

数据范围：

考虑用经典 来解决计数问题。从 开始到任意接受状态组成的字符串一定都是该序列的子序列，所以只要当前 ，则答案计数。

记录状态 表示当前分别在三个字符串的第 位往后的答案，如果非空则统计答案即可，可以使用记忆化来实现。

AC Code

// ----- Eternally question-----
// Problem: P1819 公共子序列
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1819
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-20 14:51:26
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10;
const int Mod=1e8;
int N,ans;
char Str[MAXN];
int Tr[3][MAXN][26],Pos[26];
inline void build(char *s,int Tr[][26])
{
	for(int c=0;c<26;++c) Pos[c]=N+1;
	for(int i=N;i;--i)
	{
		for(int c=0;c<26;++c) Tr[i][c]=Pos[c];
		Pos[s[i]-'a']=i;
	}
	for(int c=0;c<26;++c) Tr[0][c]=Pos[c];
}
int Dp[MAXN][MAXN][MAXN];
inline int Max(int a,int b,int c){ return std::max(std::max(a,b),c); }
int Dfs(int a,int b,int c)
{
	if(Max(a,b,c)==N+1) return 0;
	if(Dp[a][b][c]) return Dp[a][b][c];
	int res=0;
	for(int s=0;s<26;++s) res=(res+Dfs(Tr[0][a][s],Tr[1][b][s],Tr[2][c][s]))%Mod;
	if(a||b||c) ++res;
	return Dp[a][b][c]=res;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=0;i<3;++i) scanf("%s",Str+1),build(Str,Tr[i]);
	write(Dfs(0,0,0));
	return 0;
}
/*

*/

---

主席树优化

如果字符集大小足够的话（如 ），则用上述方法肯定是行不通的。考虑结合数据结构进行维护。容易发现，当我们维护 的 时，其与 的 当且仅当存在一个字符的转移不同，这样的话，我们可以考虑全盘继承 的转移函数后进行单点修改，这个过程可以使用可持久化线段树实现，可以将复杂度降到 。

还是以例题来讲吧。

题目简介

题目名称：子序列自动机 /

题目来源：洛谷 /

评测链接 ：https://www.luogu.com.cn/problem/P5826
评测链接 ：https://www.luogu.com.cn/problem/P3500

给定一个长度为 的序列，共 次询问，询问一个长度为 的序列 是否是 的子序列，值域 。

数据范围：

用主席树维护子序列自动机，然后暴力跳即可。时间复杂度 。

AC Code

// ----- Eternally question-----
// Problem: P5826 【模板】子序列自动机
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5826
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// Written by: Eternity
// Time: 2023-05-20 15:22:32
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=1e5+10;
int Type,N,M,Q,Pos[MAXN],a[MAXN];
int Rt[MAXN],Idx;
#define ls(p) Tr[p].lc
#define rs(p) Tr[p].rc
struct PST
{ int lc,rc,val; }Tr[MAXN<<5];
void build(int &p,int l,int r)
{
	p=++Idx;
	if(l==r) return Tr[p].val=N+1,void();
	int mid=(l+r)>>1;
	build(ls(p),l,mid),build(rs(p),mid+1,r);
}
void modifyX(int &p,int l,int r,int x,int c)
{
	Tr[++Idx]=Tr[p],p=Idx;
	if(l==r) return Tr[p].val=c,void();
	int mid=(l+r)>>1;
	x<=mid?modifyX(ls(p),l,mid,x,c):modifyX(rs(p),mid+1,r,x,c);
}
int queryX(int p,int c,int l,int r)
{
	if(l==r) return Tr[p].val;
	int mid=(l+r)>>1;
	return c<=mid?queryX(ls(p),c,l,mid):queryX(rs(p),c,mid+1,r);
}
inline void init()
{
	for(int i=1;i<=M;++i) Pos[i]=N+1;
	build(Rt[N],1,M),Pos[a[N]]=N;
	for(int i=N-1;~i;--i)
	{
		Rt[i]=Rt[i+1],Pos[a[i]]=i;
		modifyX(Rt[i],1,M,a[i+1],Pos[a[i+1]]);
	}
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(Type,N,Q,M);
	for(int i=1;i<=N;++i) read(a[i]);
	init();
	for(int len,x;Q--;)
	{
		read(len);
		int u=0,flag=0;
		while(len--)
		{
			read(x);
			if(u==N+1) flag=1;
			else u=queryX(Rt[u],x,1,M);
		}
		if(flag||u==N+1) puts("No");
		else puts("Yes");
	}
	return 0;
}
/*

*/

这个题有一个离线的线性做法，可以考虑多路归并，用双指针分别在 上向后扫，同时得到答案即可。用 个 std::vector<Pir>vec[] 记录需要匹配 的所有询问串的信息，编号和当前位。在枚举 的时候一一匹配即可，均摊出来时间复杂度为 。

因为 的长度为动态的，所以考虑压到一个数组里方便存储。

AC Code

// ----- Eternally question-----
// Problem: P3500 [POI2010]TES-Intelligence Test
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3500
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-05-20 15:43:03
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
#define fir first
#define sec second
using Pir=std::pair<int,int>;
const int MAXN=1e6+10;
int N,Q,L,a[MAXN],b[MAXN],St[MAXN];
std::vector<Pir>vec[MAXN],Cpy;
bool ans[MAXN];
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N);
	for(int i=1;i<=N;++i) read(a[i]);
	read(Q);
	for(int i=1,len;i<=Q;++i)
	{
		read(len),St[i]=L+1;
		for(int i=1,x;i<=len;++i) read(x),b[++L]=x;
		vec[b[St[i]]].emplace_back((Pir){i,St[i]}); 
	}
	St[Q+1]=L+1;
	for(int i=1;i<=N;++i)
	{
		Cpy.clear();
		for(auto x:vec[a[i]])
		{
			int k=x.fir,p=x.sec;
			if(p+1==St[k+1]) ans[k]=1;
			else Cpy.emplace_back((Pir){k,p+1});
		}
		vec[a[i]].clear();
		for(auto x:Cpy)
		{
			int k=x.fir,p=x.sec;
			vec[b[p]].emplace_back((Pir){k,p});
		}
	}
	for(int i=1;i<=Q;++i) puts(ans[i]?"TAK":"NIE");
	return 0;
}
/*

*/

---