锐客网

  1. 首页 > it技术 > >

基本算法|wiki oi 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
题目大意：
最开始看见题目是这样想的.......给出了n个字符串分别算出n个字符串的前i个字母的哈希值，在leni 首先对于整个的字符串进行一个排序，排序的规则是自己写的：

bool operator < (node b,node c) { for(int i=0; ic.a[i]) return false; } return b.len

相当于是重载了<符号，然后最后sort 的时候是调用了< 符号，也顺便理解了一下原来的sort中若是直接排序就默认调用<符号，所以是从小到大排序的，这个重载函数也就相当于之前写过的cmp函数，不过cmp函数需要在sort函数后面加上，而<符号是直接调用的。
排完序之后是这样的：
i
a
int
able
inter


排完序之后是：
a
able
i
int
inter

然后在说一点：这可不是字典序........自己一直以为这是字典序....... 字典序是a 这样之后对于拍好序的数进行一个遍历就行，遍历的规则是若是栈元素数量是0，就进栈，下一个元素就是和栈顶元素比较，若是其hash的前几个值都相同，并且下一个元素的长度大于栈顶元素，则这个元素进栈，否则出栈。最后用一个max记录top所能达到的最大值就行了.......
想法很好.......大赞！

#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; ic.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++) cout<



【基本算法|wiki oi 1051 接龙游戏】

    推荐阅读


    上一篇：Log4j使用方式详解

    下一篇：kafka(3) -- 连接导入、导出数据