SP8093 JZPGYZ - Sevenk Love Oimaster(广义后缀自动机)

题意

题目链接

Sol

广义后缀自动机板子题。。和BZOJ串那个题很像

首先建出询问串的SAM，然后统计一下每个节点被多少个串包含

最后直接拿询问串上去跑就行了

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;

int N, Q;

string s[MAXN], t[MAXN];

int fa[MAXN], len[MAXN], ch[MAXN][26], tim[MAXN], val[MAXN], root = 1, las = 1, tot = 1;

void insert(int x) {

	int now = ++tot, pre = las; las = now; len[now] = len[pre] + 1;

	for(; pre && !ch[pre][x]; pre = fa[pre]) ch[pre][x] = now;

	if(!pre) fa[now] = root;

	else {

		int q = ch[pre][x];

		if(len[pre] + 1 == len[q]) fa[now] = q;

		else {

			int nq = ++tot; fa[nq] = fa[q]; len[nq] = len[pre] + 1;

			memcpy(ch[nq], ch[q], sizeof(ch[q]));

			fa[q] = fa[now] = nq;

			for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nq;

		}

	}

}

int main() {

	cin >> N >> Q;

	for(int i = 1; i <= N; i++) {

		cin >> s[i]; las = 1;

		for(int j = 0; j < s[i].length(); j++) insert(s[i][j] - 'a');

	}

	for(int i = 1; i <= N; i++) {

		string ns = s[i]; int now = root;

		for(int j = 0; j < ns.length(); j++) {

			int x = ns[j] - 'a';

			now = ch[now][x];

			for(int p = now; p && tim[p] != i; p = fa[p])

				tim[p] = i, val[p]++;

		}

	}

	for(int i = 1; i <= Q; i++) {

		string ns; cin >> ns;

		int now = root, flag = 0;

		for(int j = 0; j < ns.length(); j++) {

			int x = ns[j] - 'a';

			if(!ch[now][x]) {flag = 1; break;}

			now = ch[now][x];

		}

		printf("%d\n", flag == 1 ? 0 : val[now]);

	}

	return 0;

}