求助(悬1关)
  • 板块灌水区
  • 楼主lccve
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/28 15:11
  • 上次更新2023/11/3 07:13:46
查看原帖
求助(悬1关)
525302
lccve楼主2023/7/28 15:11

ac自动机(简单)

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans; 
string s,ss,t;//s是要匹配的串,t是文本
struct _node{
	int fail;
	int vis[26];
	int end;//有几个匹配串以该结点结尾
}node[1000001];
queue<int> bfs;//构建fail指针是的bfs队列
void build()//trie
{
	cin>>n;
	int u=1;
	int tot=1;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		ss=' '+s;
		int len=s.size();
		for(int j=1;j<=len;j++)
		{
			int c=ss[i]-'a';
			if(!node[u].vis[c]) node[u].vis[c]=++tot; 
			u=node[u].vis[c];
		}
		node[u].end++;
	}
	cin>>t;
	return;
}
void query()//构建fail指针
{
	int u=1;
	bfs.push(1);
	for(int i=0;i<26;i++)
		node[0].vis[i]=1;
	while(!bfs.empty())
	{
		u=bfs.front();
		bfs.pop();
		for(int i=0;i<=25;i++)
		{
			if(!node[u].vis[i]) node[u].vis[i]=node[node[u].fail].vis[i];
			else{
				bfs.push(node[u].vis[i]);
				int v=node[u].fail;
				while(v>0&&!node[v].vis[i]) v=node[v].fail;
				node[node[u].vis[i]].fail=node[v].vis[i];
			} 
		}
	}
	return;
}
void pipei()
{
	int u=1;
	int c;
	int k;
	ss=' '+t;
	int len=t.size();
	for(int i=1;i<=len;i++)
	{
		c=ss[i]-'a';
		k=node[u].vis[c];
		while(k>1)
		{
			ans+=node[u].end;
			node[u].end=0;
			k=node[u].fail;
		}
		u=node[u].vis[c];
	}
	return;
}
int main(){
	build();
	query();
	pipei();
	cout<<ans;
}

输完数据就卡住了,光标在闪但是出不了答案。

2023/7/28 15:11
加载中...