CODEVS-1051 接龍游戲

CODEVS-1051 接龍游戲

題目描述 Description

給出了N個單詞，已經按長度排好了序。如果某單詞i是某單詞j的前綴，i->j算一次接龍(兩個相同的單詞不能算接龍)。

你的任務是：對於輸入的單詞，找出最長的龍。

輸入描述 Input Description

第一行為N(1<=N<=10⁵)。以下N行每行一個單詞（由小寫組成），已經按長度排序。(每個單詞長度<50)

輸出描述 Output Description

僅一個數，為最長的龍的長度。

樣例輸入 Sample Input

5

i

a

int

able

inter

樣例輸出 Sample Output

3

數據范圍及提示 Data Size & Hint

1<=N<=10⁵

首先對字符串按照字典序排序，那麼具有相同前綴的字符串會挨在一起，然後用一個字符串棧存儲龍的長度。

/*
作者:NowAndForever
題目:p1051 接龍游戲
*/
#include
#include
#include
#include
#include
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;iinput;//便於保存字符串和排序
	for(i=0;imap;//定義一個字符串棧
    int ret=0;
	for(i=0;iret)//在這期間統計棧最多有多少個元素
			ret=map.size();
	}
		printf("%d\n",ret);
	return 0;
}