这题有点意思

思路

题目要求求字符串的“相似字符串”的个数，注意到算法标签要求字符串相同，考虑字典树 （他好像写题目名上了）

那如何做呢？
很好发现，同一个字符串的相似字符串的数量是恒定的，大约$53|W_i|$，考虑枚举每一个相似字符串，再在字典树上寻找每一个相似字符串即可。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,id;
int ch[N][26],ed[N];
string s;
void ins(string s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int &j=ch[p][s[i]-'a'];
		if(!j)j=++id;
		p=j;
	}
	ed[p]++;
}
int query(string s)
{
	int p=0;
	for(int i=0;s[i];i++)
	{
		int j=ch[p][s[i]-'a'];
		if(!j)return 0;
		p=j;
	}
	return ed[p];
}
int calc(string s)
{
	int res=0;
	for(int i=0;s[i];i++)
	{
		if(i&&s[i]==s[i-1])continue;
		string t=s.substr(0,i)+s.substr(i+1);
		res+=query(t);
	}
	for(int i=0;i<=(int)(s.size());i++)
	{
		for(char c='a';c<='z';c++)
		{
			if(c==s[i])continue;
			string t=s.substr(0,i)+c+s.substr(i);
			res+=query(t);
		}
	}
	for(int i=0;s[i];i++)
	{
		for(char c='a';c<='z';c++)
		{
			if(c==s[i])continue;
			string t=s;
			t[i]=c;
			res+=query(t);
		}
	}
	return res;
}
signed main()
{
	_sleep(1); 
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		ins(s);
	}
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		if(query(s))puts("-1");
		else cout<<calc(s)<<'\n';
	}
	return 0;
}