codevs1051接龙游戏

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

人生在世不称意，明朝散发弄哈希

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define LL long long const LL MOD1=10000007; const LL MOD2=9999993; const LL seed1=137; const LL seed2=331; int n, ans; int f1[MOD1+10], f2[MOD2+10]; char ch[100]; void work() { int Max=0; LL hs1=0,hs2=0; int j=strlen(ch); for(int i=0;i<j;++i)//枚举单词ch中的每个字母 { hs1=(seed1*hs1+ch[i]-'a'+1) % MOD1; hs2=(seed2*hs2+ch[i]-'a'+1) % MOD2; if(i==j-1 && f1[hs1] && f2[hs2]) break; if(f1[hs1]!=f2[hs2]) continue; if(f1[hs1]+1>Max) Max=f1[hs1]+1; } f1[hs1]=f2[hs2]=Max; if(ans<f1[hs1]) ans=f1[hs1]; } int main() { scanf("%d\n",&n); for(int i=1;i<=n;++i) { scanf("%s",ch); work(); } cout<<ans; return 0; }