自动搬运

查看原文

来自洛谷，原作者为

	fzwfzwfzw Haven't AFO yet.

搬运于2025-08-24 21:27:57，当前版本为作者最后更新于2020-06-09 19:52:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这是一道trie树的题目：

P4407 [JSOI2009]电子字典这一道题的变化和4407的变化是一样的！

单词的变化有三种：1删掉一个字母，2：插入一个字符，3：将一个字符变成另外一个字符

因为单词接龙的顺序是限定的（字典序），所以我们可以将可以互相变化的字符串连起来，顺序限定所以方向是一定的，举个例子

因为dig可以变化为fig

所以dig向fig连一条边，因为dig的字典序小于fig，所以，是dig连向fig的有向边，不能是fig连向dig

在这样连完所有边之后，就可以发现这是一个DAG（有向无环图）所以，这里面的最长的单词接龙就是将他拓扑排序过后的最长链啦！

下面是代码时间！

下面的三个find分别是表示三种变化，其他的是trie的基本操作

从queue开始就是拓扑排序啦！

#include<bits/stdc++.h>
using namespace std;
int read()
{
	char c;
	int w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	int ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
int vis[250005];
struct node
{
	int to[26];
	int cu;
}e[250005];
string a[250005];
int cnt;
int n,mm;
int cst;
int ooo;
int ins(int x,int y)
{
	if(!e[x].to[y])
	e[x].to[y]=++cnt;
	return e[x].to[y];
}
int last;
int www;
void inser(string w,int p)
{
	last=0;
	www=w.size();
	for(int i=0;i<www;i++)
	{
		last=ins(last,w[i]-'a');
	}
	e[last].cu=p;
}
int fid(int x,int y)
{
	if(!e[x].to[y])
	return -2;
	return e[x].to[y];
}
int find(string w)
{
	last=0;
	www=w.size();
	for(int i=0;i<www;i++)
	{
		last=fid(last,w[i]-'a');
		if(last==-2)
		{
			return 0;
		}
	}
	if(ooo)
	{
		if(vis[last]!=cst)
		{
			vis[last]=cst;
			return e[last].cu;
		}
		else return 0;
	}
	return e[last].cu;
}
int find1(string w,int aw)
{
	last=0;
	www=w.size();
	for(int i=0;i<www;i++)
	{
		if(i!=aw)
		{
			last=fid(last,w[i]-'a');
			if(last==-2)
			{
				return 0;
			}
		}
	}
	if(ooo)
	{
		if(vis[last]!=cst)
		{
			vis[last]=cst;
			return e[last].cu;
		}
		else return 0;
	}
	return e[last].cu;
}
int find2(string w,int aw,int pp)
{
	last=0;
	www=w.size();
	for(int i=0;i<www;i++)
	{
		if(i==aw)
		{
			last=fid(last,pp);
			if(last==-2)
			{
				return 0;
			}
		}
		last=fid(last,w[i]-'a');
		if(last==-2)
		{
			return 0;
		}
	}
	if(aw==www)
	{
		last=fid(last,pp);
		if(last==-2)
		{
			return 0;
		}
	}
	if(ooo)
	{
		if(vis[last]!=cst)
		{
			vis[last]=cst;
			return e[last].cu;
		}
		else return 0;
	}
	return e[last].cu;
}
int find3(string w,int aw,int pp)
{
	last=0;
	www=w.size();
	for(int i=0;i<www;i++)
	{
		if(i==aw)
		{
			last=fid(last,pp);
			if(last==-2)
			{
				return 0;
			}
		}
		else 
		{
			last=fid(last,w[i]-'a');
			if(last==-2)
			{
				return 0;
			}
		}
	}
	if(ooo)
	{
		if(vis[last]!=cst)
		{
			vis[last]=cst;
			return e[last].cu;
		}
		else return 0;
	}
	return e[last].cu;
}
struct nod
{
	int next,to;
}ew[1000005];
int ppp;
int h[1000005];
int rd[1000005];
void add(int x,int y)
{
	if(!y)return;
	ppp++;
	ew[ppp].next=h[x];
	h[x]=ppp;
	ew[ppp].to=y;
	rd[y]++;
}
int longest[1000005];
int main(){
	n=read();
	char c[18];
	for(int i=1;i<=n;i++)
	{
		scanf("%s",c);
		a[i]=c;
	}
	inser(a[n],n);
	for(int iw=n-1;iw>=1;iw--)
	{
		cst++;
		ooo=1;
		string w=a[iw];
		int o=a[iw].size();
		for(int i=0;i<o;i++)
		{
			add(iw,find1(w,i));
		}
		for(int i=0;i<=o;i++)
		{
			for(int j=0;j<26;j++)
			{
				add(iw,find2(w,i,j));
			}
		}
		for(int i=0;i<o;i++)
		{
			for(int j=0;j<26;j++)
			{
				add(iw,find3(w,i,j));
			}
		}
		inser(a[iw],iw);
	}
	queue<int>q;
	for(int i=1;i<=n;i++)
	{
		if(!rd[i])
		{
			q.push(i);
		}
	}
	while(!q.empty())
	{
		int f=q.front();
		q.pop();
		longest[f]++;
		for(int i=h[f];i;i=ew[i].next)
		{
			rd[ew[i].to]--;
			if(!rd[ew[i].to])q.push(ew[i].to);
			longest[ew[i].to]=max(longest[ew[i].to],longest[f]);
		}
	}
	int maxx=0;
	for(int i=1;i<=n;i++)
	{
		maxx=max(maxx,longest[i]);
	}
	cout<<maxx<<endl;
	return 0;
}

祝大家好运