CODEVS-1051 接龙游戏

首先对字符串按照字典序排序，那么具有相同前缀的字符串会挨在一起，然后用一个字符串栈存储龙的长度。

/*
作者: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;
}