luoguP4407 [JSOI2009] 电子字典 解题报告

标签：luoguP4407 连边 匹配 map int JSOI2009 unordered 电子字典 节点

传送门

题意

对于多个字符串，查询其在字典树上的存在性或删除/插入/替换一个字符后存在的个数。

思路

存在性好说，直接在 Trie 树上做一遍查找即可。那剩下的三个操作怎么办呢？分类讨论吧。

删除

该操作等同于在匹配时越过 \(S_i\) ，剩余的字符与当前匹配节点和连边继续匹配。

插入

该操作等同于在匹配时越过 Trie 树的这一节点，剩余的字符与该节点的子节点和连边进行匹配。

替换

该操作等同于在匹配时越过 \(S_i\) ，剩余的字符与当前匹配节点的子节点和连边进行匹配。

代码

利用循环实现。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T=1,n,m,nxt[200010][30],cnt,p,ans;
bool bk[200010];
string s;
unordered_map<string,bool> mp;
unordered_map<string,bool> ANS;
unordered_map<int,bool> vis;
void add(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int k=s[i]-'a';
		if(!nxt[p][k]) nxt[p][k]=++cnt;
		p=nxt[p][k];
	}
	bk[p]=1;
}
void changee(string s,string t){
	p=0;
	for(int i=0;i<s.size();i++){
		int k=s[i]-'a';
		if((!nxt[p][k])&&(i!=s.size()-1)) return ;
		if(i!=s.size()-1) p=nxt[p][k];
	}
	for(int i=0;i<26;i++){
		if(nxt[p][i]){
			bool pd=0;
			int q=nxt[p][i];
			for(int m=0;m<t.size();m++){
				int k=t[m]-'a';
				if(!nxt[q][k]) {
					pd=1;
					break;
				}
				q=nxt[q][k];
			}
			if((!pd)&&(bk[q])){
					ans++;
			}
		}
	}
}
void pluss(string s,string t){
	bool pd=0;
	p=0;
	for(int i=0;i<s.size();i++){
		int k=s[i]-'a';
		if((!nxt[p][k])&&(i!=s.size()-1)) return ;
		if(i==s.size()-1&&(!nxt[p][k])) pd=1;
		else p=nxt[p][k];
	}
	if(pd){
		for(int i=0;i<26;i++){
			if(nxt[p][i]){
				p=nxt[p][i];
				for(int i=0;i<26;i++){
					if(nxt[p][i]){
						bool pd=0;
						int q=nxt[p][i];
						for(int m=0;m<t.size();m++){
							int k=t[m]-'a';
							if(!nxt[q][k]) {
								pd=1;
								break;
							}
							q=nxt[q][k];
						}
						if((!pd)&&(bk[q])&&(!vis[q])){
							vis[q]=1;
							ans++;
						}
					}
				}
			}
		}
	}
	else{
		for(int i=0;i<26;i++){
			if(nxt[p][i]){
				bool pd=0;
				int q=nxt[p][i];
				for(int m=0;m<t.size();m++){
					int k=t[m]-'a';
					if(!nxt[q][k]) {
						pd=1;
						break;
					}
					q=nxt[q][k];
				}
				if((!pd)&&(bk[q])&&(!vis[q])){
						vis[q]=1;
						ans++;
				}
			}
		}
	}
}
void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s;
		add(s);
		ANS[s]=1;
	}
	for(int i=1;i<=m;i++){
		mp.clear();
		vis.clear();
		ans=0;
		cin>>s;
		if(ANS[s]) {
			cout<<-1<<endl;
			continue;
		}
		for(int i=0;i<s.size();i++){//delete
			string k=s;
			k.erase(i,1);
			if(!mp[k]) ans+=ANS[k];
			mp[k]=1;
		}
		for(int i=0;i<s.size();i++){//change
			changee(s.substr(0,i),s.substr(i+1));
		}
		for(int i=0;i<=s.size();i++){//plus
			pluss(s.substr(0,i),s.substr(i));
		}
		cout<<ans<<endl;
	}
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(T--){
		solve();
	}
	return 0;
}

很好，只有 10pts。

标签：luoguP4407,连边,匹配,map,int,JSOI2009,unordered,电子字典,节点
From： https://www.cnblogs.com/wh2t3zz/p/16652164.html