自动搬运

查看原文

来自洛谷，原作者为

	stoorz **

搬运于2025-08-24 21:49:35，当前版本为作者最后更新于2020-02-27 21:01:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑暴力。对于每一个询问，我们都维护两个指针，分别扫描原串 $a$ 和询问的串 $b$。如果 $a[i]=b[j]$，那么两个指针都往后扫，否则仅 $a$ 的指针往后扫即可。

时间复杂度 $O(nm)$。

容易发现，其实没必要对于每一个询问的串都扫描一次 $a$，我们其实可以只扫描一次 $a$，对于 $a$ 的每一位，分别去匹配每一个 $b$ 即可。 具体一点，设一个串 $b_i$ 的前 $x$ 位都被扫完并比配了，我们就需要在 $a$ 串中找到下一个 $b_i[x+1]$ 的位置。

扫描 $a$ 串，设现在扫描到第 $i$ 位，$b_i$ 串已经匹配完前 $num_i$ 个位置了。那么所有 $a_i=b_j[num_j]$ 的 $b_j$ 第 $num_j$ 位就匹配上了，对于这些 $b_j$，我们将 $num_j$ 加一即可。

如何求出扫描到第 $i$ 位时有哪些 $b$ 串满足正好需要匹配 $a_i$ 呢？用 $\operatorname{vector}$ 即可。设 $pos[x]$ 表示现在需要匹配数字 $x$ 的 $b$ 串有哪些，对于 $a_i=k$，我们将 $pos[k]$ 里面的 $b$ 全部往下匹配一个位置即可。

时间复杂度 $O(n+\sum^{m}_{i=1}len[i])$。其中 $len[i]$ 表示第 $i$ 个 $b$ 串的长度。

#include <cstdio>
#include <vector>
#include <cctype>
#include <cstring>
#include <algorithm>
#define mp make_pair
using namespace std;

const int N=1000010;
int n,m,len,a[N],b[N],st[N];
bool ans[N];
vector<pair<int,int> > pos[N],cpy;
// pos[x][j].first 表示第 j 个需要匹配的数字为 x 的 b 串编号是几
// pos[x][j].second 表示第 j 个需要匹配的数字为 x 的 b 串 现在匹配到哪个位置了

int read()
{
	int d=0,f=1; char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) d=(d<<1)+(d<<3)+ch-48,ch=getchar();
	return f*d;
}

int main()
{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	m=read();
	for (int i=1,x;i<=m;i++)
	{
		x=read(); st[i]=len+1;  //省空间，将所有 b 串压缩在一个数组里
		for (int j=1;j<=x;j++)
			b[++len]=read();
		pos[b[st[i]]].push_back(mp(i,st[i]));
        // 一开始所有串都匹配到第一个位置
	}
	st[m+1]=len+1;
	for (int i=1;i<=n;i++)
	{
		cpy.clear();
		for (int j=0;j<pos[a[i]].size();j++)  // 枚举所有能匹配的串
		{
			int k=pos[a[i]][j].first,p=pos[a[i]][j].second;
			if (p+1==st[k+1]) ans[k]=1;  // 这个串已经全部匹配完了
				else cpy.push_back(mp(k,p+1));  //记录匹配下一位
		}
		pos[a[i]].clear();
		for (int j=0;j<cpy.size();j++)  //将上面匹配的串的下一位插入
		{
			int k=cpy[j].first,p=cpy[j].second;
			pos[b[p]].push_back(mp(k,p));
		}
	}
	for (int i=1;i<=m;i++)
		if (ans[i]) printf("TAK\n");
			else printf("NIE\n");
	return 0;
}