进士侯任(20ptsWA)
查看原帖
进士侯任(20ptsWA)
300370
flyfreemrn楼主2024/12/10 21:18

模式串可能有相同的，要用vector记录以每个节点为结尾的模式串 WA20pts:

using namespace std;
#define ll long long
#define MAXN 10000010
#define debug cout<<"王羽丰螳臂\n";
ll char_map[30];
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node_arr{
	ll s[MAXN],siz;
	ll lowbit(ll now){
		return now&(-now);
	}
	void add(ll now,ll val){
		while(now<=siz){
			s[now]+=val;
			now+=lowbit(now);
		}
	}
	ll result(ll now){
		ll rez=0;
		while(now>0){
			rez+=s[now];
			now-=lowbit(now);
		}
		return rez;
	}
}arr;
struct node_trea{
	ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
	ll idx,stp;
	ll dfn[MAXN],lst[MAXN];
	void build(ll x,ll y){
		nxt[++idx]=hd[x];
		ed[idx]=y;
		hd[x]=idx;
	}
	void dfs(ll now,ll p){
		lst[now]=dfn[now]=++stp;
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(y==p)continue;
			dfs(y,now);
			lst[now]=max(lst[now],lst[y]);
		}
	}
	ll result(ll x){
//		cout<<"res:"<<x<<" "<<dfn[x]<<" "<<lst[x]<<" "<<arr.result(lst[x])-arr.result(dfn[x]-1)<<endl;
		return arr.result(lst[x])-arr.result(dfn[x]-1);
	}
	void add(ll x){
		if(x)arr.add(dfn[x],1);
	}
}trea;
struct node_AC{
	ll ch[MAXN][4],it[MAXN],vis[MAXN],ans[MAXN],maxz[MAXN],dep[MAXN];
	ll idx,siz;
	void insert(string s,ll id){
		ll len=s.length(),p=0;
		for(int i=0;i<len;i++){
			ll now=char_map[s[i]-'A'+1];
			if(!ch[p][now])ch[p][now]=++idx,dep[idx]=dep[p]+1;
			p=ch[p][now];
		}
		vis[p]=id;
		siz=id;
	}
	void mk(){
		queue<ll> q;
		for(int i=0;i<4;i++){
			if(ch[0][i])q.push(ch[0][i]);
		}
		while(!q.empty()){
			ll now=q.front();
			q.pop();
			trea.build(it[now],now);
			for(int i=0;i<4;i++){
				if(ch[now][i]){
					it[ch[now][i]]=ch[it[now]][i];
					q.push(ch[now][i]);
				}else ch[now][i]=ch[it[now]][i];
			}
		}
		arr.siz=idx;
		trea.dfs(0,0);
	}
	void match(string s){
		ll len=s.length(),p=0;
		for(int i=0;i<len;i++){
			ll now=char_map[s[i]-'A'+1];
			p=ch[p][now];
			trea.add(p);
		}
	}
	void bfs(){
		queue<ll> q;
		for(int i=0;i<4;i++)if(ch[0][i])q.push(ch[0][i]);
		while(!q.empty()){
//			cout<<n<<endl;
			ll now=q.front();
			q.pop();
//			cout<<now<<endl;
			if(trea.result(now))maxz[now]=dep[now];
			if(vis[now])ans[vis[now]]=maxz[now];
			for(int i=0;i<4;i++){
				if(ch[now][i]!=ch[it[now]][i]){
					maxz[ch[now][i]]=maxz[now];
					q.push(ch[now][i]);
				}
			}
		}
		for(int i=1;i<=siz;i++)cout<<ans[i]<<endl;
	}
}AC;
ll n,m,id[MAXN];
string s,mc;
int main(){
	char_map['E'-'A'+1]=0,char_map['S'-'A'+1]=1,char_map['W'-'A'+1]=2,char_map['N'-'A'+1]=3;
	cin>>n>>m;
	cin>>mc;
	for(int i=1;i<=m;i++){
		cin>>s;
		AC.insert(s,i);
	}
	AC.mk();
//	debug;
//	cin>>s;
	AC.match(mc);
//	debug;
	AC.bfs();
	return 0;
}

ACcode

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 10000010
#define debug cout<<"王羽丰螳臂\n";
ll char_map[30];
inline ll read(){
	ll x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
struct node_arr{
	ll s[MAXN],siz;
	ll lowbit(ll now){
		return now&(-now);
	}
	void add(ll now,ll val){
		while(now<=siz){
			s[now]+=val;
			now+=lowbit(now);
		}
	}
	ll result(ll now){
		ll rez=0;
		while(now>0){
			rez+=s[now];
			now-=lowbit(now);
		}
		return rez;
	}
}arr;
struct node_trea{
	ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
	ll idx,stp;
	ll dfn[MAXN],lst[MAXN];
	void build(ll x,ll y){
		nxt[++idx]=hd[x];
		ed[idx]=y;
		hd[x]=idx;
	}
	void dfs(ll now,ll p){
		lst[now]=dfn[now]=++stp;
		for(int i=hd[now];i;i=nxt[i]){
			ll y=ed[i];
			if(y==p)continue;
			dfs(y,now);
			lst[now]=max(lst[now],lst[y]);
		}
	}
	ll result(ll x){
//		cout<<"res:"<<x<<" "<<dfn[x]<<" "<<lst[x]<<" "<<arr.result(lst[x])-arr.result(dfn[x]-1)<<endl;
		return arr.result(lst[x])-arr.result(dfn[x]-1);
	}
	void add(ll x){
		if(x)arr.add(dfn[x],1);
	}
}trea;
struct node_AC{
	ll ch[MAXN][4],it[MAXN],ans[MAXN],maxz[MAXN],dep[MAXN];
	ll idx,siz;
	vector<ll> vis[MAXN];
	void insert(string s,ll id){
		ll len=s.length(),p=0;
		for(int i=0;i<len;i++){
			ll now=char_map[s[i]-'A'+1];
			if(!ch[p][now])ch[p][now]=++idx,dep[idx]=dep[p]+1;
			p=ch[p][now];
		}
//		vis[p]=id;
		vis[p].push_back(id);
		siz=id;
	}
	void mk(){
		queue<ll> q;
		for(int i=0;i<4;i++){
			if(ch[0][i])q.push(ch[0][i]);
		}
		while(!q.empty()){
			ll now=q.front();
			q.pop();
			trea.build(it[now],now);
			for(int i=0;i<4;i++){
				if(ch[now][i]){
					it[ch[now][i]]=ch[it[now]][i];
					q.push(ch[now][i]);
				}else ch[now][i]=ch[it[now]][i];
			}
		}
		arr.siz=idx;
		trea.dfs(0,0);
	}
	void match(string s){
		ll len=s.length(),p=0;
		for(int i=0;i<len;i++){
			ll now=char_map[s[i]-'A'+1];
			p=ch[p][now];
			trea.add(p);
		}
	}
	void bfs(){
		queue<ll> q;
		for(int i=0;i<4;i++)if(ch[0][i])q.push(ch[0][i]);
		while(!q.empty()){
//			cout<<n<<endl;
			ll now=q.front();
			q.pop();
//			cout<<now<<endl;
			if(trea.result(now))maxz[now]=dep[now];
			if(vis[now].size())for(int i=0;i<vis[now].size();i++)ans[vis[now][i]]=maxz[now];
			for(int i=0;i<4;i++){
				if(ch[now][i]!=ch[it[now]][i]){
					maxz[ch[now][i]]=maxz[now];
					q.push(ch[now][i]);
				}
			}
		}
		for(int i=1;i<=siz;i++)cout<<ans[i]<<endl;
	}
}AC;
ll n,m,id[MAXN];
string s,mc;
int main(){
	char_map['E'-'A'+1]=0,char_map['S'-'A'+1]=1,char_map['W'-'A'+1]=2,char_map['N'-'A'+1]=3;
	cin>>n>>m;
	cin>>mc;
	for(int i=1;i<=m;i++){
		cin>>s;
		AC.insert(s,i);
	}
	AC.mk();
//	debug;
//	cin>>s;
	AC.match(mc);
//	debug;
	AC.bfs();
	return 0;
}
2024/12/10 21:18