1051 接龙游戏

1051 接龙游戏

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<cstring>
 5 #include<algorithm>
 6 using namespace std;
 7 string a[1000001];
 8 int tot=1;
 9 stack<int>s;
10 int main()
11 {
12     int n;
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++)
15     {
16         //scanf("%s",a[i]);
17         cin>>a[i];
18     }
19     sort(a+1,a+n+1);
20     s.push(1);
21     for(int i=2;i<=n;i++)
22     {
23         while(!s.empty())
24         {
25             int t=s.top();
26             int flag=0;
27             if(a[t].size()<a[i].size())
28             {
29                 if(a[i].find(a[t])==0)
30                 {
31                     break;
32                 }
33                 else
34                 {
35                     flag=1;
36                 }
37             }
38             else flag=1;
39             if(flag==0)
40             break;
41             if(flag==1)
42             {
43                 s.pop();
44             }
45         }
46         s.push(i);
47         if(s.size()>tot)
48         tot=s.size();
49     }
50     cout<<tot;
51     return 0;
52 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端架构与工程

【翻译】ES6生成器简介

原文地址:http://davidwalsh.name/es6-generators ES6生成器全部文章: The Basics Of ES6 Generat...

21570
来自专栏黑泽君的专栏

java基础学习_IO流03_字符流、IO流小结、案例_day21总结

11420
来自专栏做全栈攻城狮

电脑小白自学软件编程-.Net语法基础之循环语句,纯技巧干货

课程总目录:因头条无法自定义目录,大家关注:“做全栈攻城狮”微信公众号。回复“.net目录”,即可获取。微信公众号也包含大量学习教程,等你来~

16540
来自专栏程序猿

Linux sed 命令的使用

首先,就昨晚的发的消息道歉,虽然整蛊大家了,但是我还是挺开心的。 sed是一种流编辑器,配合正则表达式使用,sed处理文件之时,把当前处理的文保存...

421100
来自专栏Java技术栈

10 道关于 Java 泛型的面试题

这是在各种Java泛型面试中,一开场你就会被问到的问题中的一个,主要集中在初级和中级面试中。那些拥有Java1.4或更早版本的开发背景的人都知道,在集合中存储对...

14220
来自专栏较真的前端

当面试官问你闭包时,他究竟想听到些什么?

38150
来自专栏信安之路

【作者投稿】奇葩webshell技巧

前段时间看XDCTF的一道web题,发现了一种很奇特的构造webshell的方法。

14700
来自专栏技术之路

c++基础 使用智能指针

三个智能指针模板(auto_ptr、unique_ptr和shard_ptr)都定义了类似指针的对象(c++11已将auto_ptr摒弃),可以将new获得(直...

21350
来自专栏一“技”之长

Swift4语法新特性 原

      随着iPhone X的来到,iOS11的发布,Swift语言也更新到了第4个版本。在Swift4中,无论是代码风格还是编程理念都更进一步的融合了许多...

30230
来自专栏企鹅号快讯

verilog编程要素整理时刻牢记

verilog编程建议 1、不使用初始化语句; 2、不使用延时语句; 3、不使用循环次数不确定的语句,如:forever,while等; 4、尽量采用同步方式设...

21580

扫码关注云+社区

领取腾讯云代金券