题意

给定一个长为 $n$ 的字符串 $s$ ，随后有 $q$ 次询问，询问对于每次输入的字符串 $t$ ，其在 $s$ 中出现的次数。

$n,\sum|t_i|,q\leq10^5$

题解

SAM 板题，把失配树子树大小跑出来直接做。

代码

const int N = 2e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int d[N], s[N];
	namespace SAM {
		int Last, tot;
		int fail[N], maxlen[N];
		unordered_map<int, int> trans[N];
		void Build() { Last = tot = 1; }
		void Insert(int c) {
			int p = Last, np = ++tot;
			s[np] = 1;
			maxlen[np] = maxlen[p] + 1;
			for (; p && !trans[p][c]; p = fail[p])
				trans[p][c] = np;
			if (!p) fail[np] = 1;
			else {
				int q = trans[p][c];
				if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
				else {
					int nq = ++tot; fail[nq] = fail[q];
					trans[nq] = trans[q];
					maxlen[nq] = maxlen[p] + 1;
					for (; p && trans[p][c] == q; p = fail[p])
						trans[p][c] = nq;
					fail[np] = fail[q] = nq;
				}
			}
			Last = np;
		}
		int query(int *a) {
			int p = 1;
			for (int i = 1; i <= a[0]; ++i) {
				if (!trans[p].count(a[i])) return 0;
				p = trans[p][a[i]];
			}
			return s[p];
		}
	}

	int n;
	int a[N];
	
	int main () {
		int op = Read();
		n = Read();
		int m = Read();
		SAM::Build();
		for (int i = 1; i <= n; i++) {
			int x = Read();
			SAM::Insert(x);
		}
		queue<int> q;
		for (int i = 1; i <= SAM::tot; i++) d[SAM::fail[i]]++;
		for (int i = 1; i <= SAM::tot; i++) if (!d[i]) q.emplace(i);
		while (!q.empty()) {
			int u = q.front(); q.pop();
			if (SAM::fail[u]) {
				s[SAM::fail[u]] += s[u];
				if (!(--d[SAM::fail[u]])) q.emplace(SAM::fail[u]);
			}
		}
		for (int lstans = 0; m--; ) {
			a[0] = Read();
			for (int i = 1; i <= a[0]; i++) a[i] = Read() ^ (op? lstans: 0);
			printf ("%d\n", lstans = SAM::query(a));
		}
		return 0;
	}
}

int main () {
	freopen("poem.in", "r", stdin);
	freopen("poem.out", "w", stdout);
	Main::main();
	return 0;
}