1051 接龙游戏

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
 
 
题目描述 Description

给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。

你的任务是:对于输入的单词,找出最长的龙。

输入描述 Input Description

第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)

输出描述 Output Description

仅一个数,为最长的龙的长度。

样例输入 Sample Input

5

i

a

int

able

inter

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

1<=N<=105

思路:

  用hash表把所有的单词给存起来

  然后比较的时候用hash表比较

  然后线性结构比较是否为前缀的复杂度为n^2

  然而n<=100000

  超时稳稳的

  那,如何优化呢?

  考虑把线性比较转化成树

  建立一个根节点

  我们从根节点找这个单词的前缀

  如果没有这个单词的前缀

  则把这个单词作为一个叶节点生长在根节点上

  如果找到了

  则跳入这个叶节点

  继续从这个叶节点找前缀

  直到找不到,然后把这个单词作为一个新的叶节点生长在当前节点上

  这样会优化很多很多

  轻松ac

来,上代码:

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream> #define mod 10000007 using namespace std; struct node {
int from,to,dis,next;
};
struct node edge[]; int n,len[],hash[][],dp[];
int head[],num,ans=; string word[]; inline void edge_add(int from,int to)
{
num++;
edge[num].to=to;
edge[num].from=from;
edge[num].next=head[from];
head[from]=num;
} void dfs(int now,int pos,int be)
{
ans=max(now,ans);
for(int i=head[be];i;i=edge[i].next)
{
if(len[edge[i].to]<len[pos])
{
if(hash[edge[i].to][len[edge[i].to]-]==hash[pos][len[edge[i].to]-])
{
dfs(now+,pos,edge[i].to);
return ;
}
}
}
edge_add(be,pos);
} int main()
{
len[]=;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
dp[i]=;
cin>>word[i];
len[i]=word[i].length();
for(int j=;j<len[i];j++)
{
hash[i][j]=word[i][j]-'a'+;
if(j) hash[i][j]+=(hash[i][j-]*)%mod;
hash[i][j]%=mod;
}
dfs(,i,);
}
cout<<ans<<endl;
return ;
}
04-30 02:14