求助
查看原帖
求助
701221
Chr0n1CleC楼主2022/10/11 14:02
#include<stdio.h>
#include<string>
#include<cstring>
#include<iostream>
#include<queue> 
using namespace std;
#define N 5000009


	queue < int > q; 
	int tr[N][26], cnt = 0;
	int e[N], fail[N];
	
	inline void insert(char* s)
	{
		int u = 0;
		for (int i = 1;s[i];i ++)
		{
		    fail[u] = -1;
			if (!tr[u][s[i] - 'a'])
				tr[u][s[i] - 'a'] = ++ cnt;
			u = tr[u][s[i] - 'a'];
		}
		e[u] ++;
	}//插入字符串,构建字典树
	
	inline void build()
	{
	    q = queue < int > ();
		for (int i = 0;i < 26;i ++)
			if (tr[0][i])
				fail[tr[0][i]] = 0, q.push(tr[0][i]);
		while (!q.empty())
		{
			int u = q.front();
			q.pop();
			for (int i = 0;i < 26;i ++)
			{
				if (tr[u][i])
					fail[tr[u][i]] = tr[fail[u]][i],
					q.push(tr[u][i]);
				else
					tr[u][i] = tr[fail[u]][i];
			}
		}
	}//构建失配指针
	
	inline int ask(char* s)
	{
		int ret = 0, u = 0;
		for (int i = 1;s[i];i ++)
		{
			u = tr[u][s[i] - 'a'];
			int j = u;
			while (j && e[j] != -1)
				ret += e[j], e[j] = -1, j = fail[j]; 
		}
		return ret;
	}

char s[N];

int main()
{
	int n;
	scanf("%d", &n);
	while (n --)
		scanf("%s", s + 1), insert(s);
	scanf("%s", s + 1);
	printf("%d", ask(s));
	
	return 0;
}

2022/10/11 14:02
加载中...