40 ,求调,字典树做法
查看原帖
40 ,求调,字典树做法
1351126
General0826楼主2024/6/27 22:32
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=2e5+5;
int tr[M][26],trt=0;
bool vis[M];
int n,m;
string s;
vector<int> vec;
void init()
{
	for(int i=0;i<vec.size();i++)
		vis[vec[i]]=1;
	vec.clear();
} 
string qp(string s,int l)
{
	string c;int len=s.size();
	for(int i=l;i<len;i++)
		c=c+s[i];
	return c;
}
void intr(string s)
{
	int cur=0,len=s.size();
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		if(tr[cur][c]==0)
			tr[cur][c]=++trt;
		cur=tr[cur][c];
	}
	vis[cur]=1;
}
bool fe(int cur,string s)
{
	int len=s.size(),lt=cur;
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		if(tr[cur][c]==0)
			return 0;
		cur=tr[cur][c];
	}
	if(vis[cur])
	{
		vec.push_back(cur);
		//cout<<s<<' '<<cur<<' '<<lt<<'\n';
		vis[cur]=0;
		return 1;
	}
	return 0;
}
int cheke(string s,int len)
{
	int cur=0,num=0;
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		num+=fe(tr[cur][c],qp(s,i-1));
		num+=fe(tr[cur][c],qp(s,i+1));
		for(int j=0;j<26;j++)
			if(j!=c)
				num+=fe(cur,char(j+'a')+qp(s,i+1));
		cur=tr[cur][c];
	}
	
	return num;
}
void dfs(int cur,string s)
{
	cout<<cur<<' '<<s<<' '<<vis[cur]<<'\n';
	for(int i=0;i<26;i++)
		if(tr[cur][i]!=0)
			dfs(tr[cur][i],s+char(i+'a'));
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		intr(s);
	}
	while(m--)
	{
		cin>>s;
		if(fe(0,s)==1)
			cout<<-1<<'\n';
		else
			cout<<cheke(s,s.size())<<'\n';
		init();
	}
}
2024/6/27 22:32
加载中...