题解 P1688 【新单词接龙问题】
这是一道trie树的题目：
P4407 [JSOI2009]电子字典这一道题的变化和4407的变化是一样的！
单词的变化有三种：1删掉一个字母，2：插入一个字符，3：将一个字符变成另外一个字符
因为单词接龙的顺序是限定的（字典序），所以我们可以将可以互相变化的字符串连起来，顺序限定所以方向是一定的，举个例子
因为dig可以变化为fig
所以dig向fig连一条边，因为dig的字典序小于fig，所以，是dig连向fig的有向边，不能是fig连向dig
在这样连完所有边之后，就可以发现这是一个DAG（有向无环图）所以，这里面的最长的单词接龙就是将他拓扑排序过后的最长链啦！
下面是代码时间！
下面的三个find分别是表示三种变化，其他的是trie的基本操作
从queue<int>开始就是拓扑排序啦！
#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;
}