wikioi 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

思路：这题就是要用到哈希函数匹配字符串是否接龙，但是在处理上感觉比较机智的是栈的应用上，因为这题刚开始我也没太懂，所以费了100积分下载了别人
的代码，研究了好久才明白。在二维字符串数组排序上，对sort函数又加深了认识，不能直接来排序，二维数组在sort中不可以直接放入排序的。栈又把时间提
高了好多，达到了线性条件。

#include 
  
   
#include 
   
     #include 
    
      #include
     
       using namespace std; struct node { int len; char a[55]; }e[100005]; int Stack[100005]; bool operator < (node b,node c) { for(int i=0;i
      
       c.a[i]) return false; } return b.len
       
        >n; for(i=1; i<=n; i++) { scanf("%s",e[i].a); e[i].len=strlen(e[i].a); } sort(e+1,e+n+1); for(i=1;i<=n;i++) { while((top)&&e[i].len<=e[Stack[top]].len||hash(e[Stack[top]].a,e[Stack[top]].len)!=hash(e[i].a,e[Stack[top]].len)) top--; Stack[++top]=i; if(sum