首页 > 代码库 > 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 接龙游戏