首页 > 代码库 > Codevs 1051 接龙游戏
Codevs 1051 接龙游戏
1051 接龙游戏
题目描述 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哪里出了错，才得了这么点分*/#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#define mod 137593233using namespace std;int n;char s[100010][60];int h[100010][60],lth[100010];int dp[100010],ans;void Hash(int k){ int len=strlen(s[k]+1); lth[k]=len; for(int i=1;i<=len;i++){ h[k][i]=(h[k][i-1]+s[k][i]-‘a‘)%mod; }}int main(){ freopen("Cola.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s[i]+1); Hash(i); } for(int i=1;i<=n;i++)dp[i]=1; for(int i=2;i<=n;i++){ for(int j=1;j<i;j++){ int len=lth[j]; if(h[j][len]==h[i][len])dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } printf("%d",ans);}
Codevs 1051 接龙游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。