给出了N个单词，已经按长度排好了序。如果某单词i是某单词j的前缀，i->j算一次接龙(两个相同的单词不能算接龙)。
你的任务是：对于输入的单词，找出最长的龙。
第一行为N(1<=N<=105)。以下N行每行一个单词（由小写组成），已经按长度排序。(每个单词长度<50)
仅一个数，为最长的龙的长度。
5
i
a
int
able
inter
3
1<=N<=105
/* 不知道我的hash哪里出了错，才得了这么点分 */ #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define mod 137593233 using 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); }
原文：http://www.cnblogs.com/thmyl/p/7191461.html
