求助,卡了几个月了
查看原帖
求助,卡了几个月了
701221
Chr0n1CleC楼主2022/10/12 13:55
#include<stdio.h>
#define N 1000009
#include<queue>
#include<cstring>

int e[N][26], cnt, sum[N], fail[N];

inline void insert(char* s)
{
	int u = 0, len = std::strlen(s);
	for (int i = 0;i < len;++ i)
	{
		int v = s[i] - 'a';
		if (!e[u][v])
			e[u][v] = ++ cnt;
		u = e[u][v];
	}
	++ sum[u];
}

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

inline int query(char* s)
{
	int u = 0, ans = 0, len = strlen(s);
	for (int i = 0;i < len;++ i)
	{
		u = e[u][s[i] - 'a'];
		int cur = u;
		while (cur && sum[cur] != 1)
			ans += sum[cur], sum[cur] = -1, cur = fail[cur];
	}
	return ans;
}

char s[N];

int main()
{
	int n;
	scanf("%d", &n);
	while (n --)
		scanf("%s", s), insert(s);
	fail[0] = 0;
	build();
	scanf("%s", s);
	printf("%d", query(s));

	return 0;
}
2022/10/12 13:55
加载中...