首页 > 代码库 > CODEVS-1051 接龙游戏
CODEVS-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
首先对字符串按照字典序排序,那么具有相同前缀的字符串会挨在一起,然后用一个字符串栈存储龙的长度。
/* 作者:NowAndForever 题目:p1051 接龙游戏 */ #include<cstdio> #include<stack> #include<string> #include<vector> #include<algorithm> using namespace std; bool pd(string a,string b)//判断字符串b是不是字符串a的子串 { int l=a.size(),i; int p=b.size(); if(l<=p)return 0;//如果a的长度小于等于b 跳出(相同的单词也不行) for(i=0;i<p;i++)//判断如果在b的范围内有不相同的情况就跳出 { if(a[i]!=b[i]) return 0; } return 1; } int main()//这就启发我们将所有单词按字典序排序,这样就使得前缀相同的单词被“挤”在一起了 { int n,i; char s[55]; scanf("%d",&n); vector<string>input;//便于保存字符串和排序 for(i=0;i<n;i++) { scanf("%s",s); input.push_back(s); } sort(input.begin(),input.end());//默认从小到大 stack<string>map;//定义一个字符串栈 int ret=0; for(i=0;i<n;i++) { //然后我们维护一个栈,枚举所有的字符串(按字典序排好的) 如果当前的字符串能和栈顶的字符串接龙的话 while(!map.empty()&&(!pd(input[i],map.top()))) //那么当前字符串入栈,继续枚举下一个字符串,如果不能接龙,那么栈顶字符串弹出, //当前字符串继续与弹出后的栈顶字符串比较,直到当前字符串与栈顶字符串能接成龙,然后当前字符串入栈, map.pop(); map.push(input[i]); if(map.size()>ret)//在这期间统计栈最多有多少个元素 ret=map.size(); } printf("%d\n",ret); return 0; }
CODEVS-1051 接龙游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。