全T求助,悬一关
查看原帖
全T求助,悬一关
701253
fulinran2026楼主2024/5/29 17:08
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e6+5;

int n,cnt=1,ans;
int v[N];
char s[N];

struct node
{
	int fail,tag;
	int ch[30];
}t[N];

inline void build_fail()
{
	queue<int> q;
	
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++)
		{
			int v=t[u].ch[i];
			if(!v) continue;
			q.push(v);
			int ti=t[u].fail;
			while(ti&&!t[ti].ch[i]) ti=t[ti].fail;
			t[v].fail=ti?t[ti].ch[i]:1;
		}
	}
	return ;
}

inline void query(char s[])
{
	int x=1;
	
	for(int i=0;i<strlen(s);i++)
	{
		int y=s[i]-'a';
		while(x&&!t[x].ch[y]) x=t[x].fail;
		x=x?t[x].ch[y]:1; y=x;
		while(y&&!v[y])
		{
			ans+=t[y].tag;
			t[y].tag=0;
			v[y]=1;
			y=t[y].fail;
		}
	}
}

signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		int rt=1;
		
		for(int j=0;j<strlen(s);j++)
		{
			int x=s[j]-'a';
			if(!t[rt].ch[x])
				t[rt].ch[x]=++cnt;
			rt=t[rt].ch[x];
		}
		t[rt].tag++;
	}
	build_fail();
	scanf("%s",s);
	query(s);
	printf("%d",ans);
	return 0;
}
2024/5/29 17:08
加载中...