时间限制: 1 s
空间限制: 128000 KB
题目等级 : 钻石 Diamond
题目描述 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
1 #include<iostream>
2 #include<cstdio>
3 #include<stack>
4 #include<cstring>
5 #include<algorithm>
6 using namespace std;
7 string a[1000001];
8 int tot=1;
9 stack<int>s;
10 int main()
11 {
12 int n;
13 scanf("%d",&n);
14 for(int i=1;i<=n;i++)
15 {
16 //scanf("%s",a[i]);
17 cin>>a[i];
18 }
19 sort(a+1,a+n+1);
20 s.push(1);
21 for(int i=2;i<=n;i++)
22 {
23 while(!s.empty())
24 {
25 int t=s.top();
26 int flag=0;
27 if(a[t].size()<a[i].size())
28 {
29 if(a[i].find(a[t])==0)
30 {
31 break;
32 }
33 else
34 {
35 flag=1;
36 }
37 }
38 else flag=1;
39 if(flag==0)
40 break;
41 if(flag==1)
42 {
43 s.pop();
44 }
45 }
46 s.push(i);
47 if(s.size()>tot)
48 tot=s.size();
49 }
50 cout<<tot;
51 return 0;
52 }