首页 > 代码库 > codevs 1051 接龙游戏(栈模拟)

codevs 1051 接龙游戏(栈模拟)

传送门

Description

给出了N个单词,已经按长度排好了序。如果某单词i是某单词j的前缀,i->j算一次接龙(两个相同的单词不能算接龙)。

你的任务是:对于输入的单词,找出最长的龙。

Input

第一行为N(1<=N<=105)。以下N行每行一个单词(由小写组成),已经按长度排序。(每个单词长度<50)

Output

仅一个数,为最长的龙的长度。

Sample Input

5

i

a

int

able

inter

Sample Output

3

思路

  某单词i是某单词j的前缀,因此可以按照字典序先排序(注:sort似乎不能对char类型的二维数组排序,有空要学学qsort的写法),然后从字典序最小的数开始枚举,看一下当前单词是否能成为下一个单词的前缀,可以则将下一个单词继续压入栈中,不行则将当前单词出栈,按照这种想法去模拟维护一个栈,更新最大值即可。

 

#include<iostream>#include<cstdio>#include<cstring>#include<stack>#include<string> #include<algorithm>using namespace std;const int maxn = 100005;string word[maxn];int main(){	int N;	while (~scanf("%d",&N))	{		stack<int>stk;		int res = 1;		for (int i = 0;i < N;i++)		{			cin >> word[i];		}		sort(word,word+N);		stk.push(0);		for (int i = 1;i < N;i++)		{			bool flag = false;			while (!stk.empty())			{				int tmp = stk.top();				int len1 = word[tmp].size();				int len2 = word[i].size();				if (len2 > len1)				{					flag = true;					for (int j = 0;j < len1;j++)					{						if (word[tmp][j] != word[i][j])						{							flag = false;							break;						}					}				}				if (flag)	break;				stk.pop();			}			stk.push(i);			int len3 = stk.size();			res = max(res,len3);		}		printf("%d\n",res);	}	return 0;} 

codevs 1051 接龙游戏(栈模拟)