题目链接：https://www.rqnoj.cn/problem/429
题意：
如果一张由一个词或多个词组成的表中，每个单词（除了最后一个）都是排在它后面的单词的前缀，则称此表为一个词链。
如：i,int,integer.
给你一堆按字典序排好的字符串，问你最长的词链有多长（词链中的字符串个数）。
题解：
单调栈。
找出单调性：
对于栈内的元素，从栈底到栈顶为单调，形成一个词链。
找出答案：
扫一遍给出的字符串，栈的最大高度即为答案。
维护单调性：
因为字符串按字典序排好，已经达到了是单调性最优的状态（贪心证明），所以就不用管扫描顺序了。
对于一个新扫到的字符串s[i]：
（1）如果满足单调性，则入栈。
即：1. 当前栈顶为s[i]的前缀(is_prefix(stk.top(),s[i]))。
2. 当前栈为空。
（2）如果不满足单调性，则弹出栈顶，直到满足单调性为止。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
#define MAX_N 10005 using namespace std; int n;
int ans;
string s[MAX_N];
stack<string> stk; void read()
{
cin>>n;
for(int i=;i<n;i++)
{
cin>>s[i];
}
} bool is_prefix(string sub,string dst)
{
if(sub.size()>dst.size()) return false;
for(int i=;i<sub.size();i++)
{
if(sub[i]!=dst[i]) return false;
}
return true;
} void solve()
{
ans=;
for(int i=;i<n;i++)
{
while(!stk.empty() && !is_prefix(stk.top(),s[i]))
{
stk.pop();
}
stk.push(s[i]);
ans=max(ans,(int)stk.size());
}
} void print()
{
cout<<ans<<endl;
} int main()
{
read();
solve();
print();
}
