题目描述
kkksc03是个非凡的空想家！在短时间内他设想了大量网页，然后总是交给可怜的lzn去实现。
洛谷的网页端，有很多文件夹，文件夹还套着文件夹。
例如：\(/luogu/application/controller\) 表示根目录下有一个名称为 \(luogu\) 的文件夹，这个文件夹下有一个名称 \(application\) 的文件夹，其中还有名为 \(controller\) 的文件夹。
每个路径的第1个字符总是 \(/\) ，且没有两个连续的 \(/\) ，最后的字符不是 \(/\) 。所有名称仅包含数字和小写字母。
目前根目录是空的。kkksc03想好了很多应该有的文件夹路径名。问题是，需要是使这些文件夹都存在，需要新建几个文件夹呢？
输入格式
输入文件第1行为一个正整数 \(N\) 。
接下来N行，每行为一个描述路径的字符串，长度均不超过 \(100\) 。
输出格式
输出应包含N行，每行一个正整数，第i行输出若要使第 \(1\) 个路径到第 \(i\) 个路径存在，最少需要新建多少个文件夹。
输入输出样例
输入 #1
2
/luogu/application/controller
/luogu/application/view
输出 #1
3
4
输入 #2
3
/chicken
/chicken/egg
/chicken
输出 #2
1
2
2
输入 #3
4
/a
/a/b
/a/c
/b/b
输出 #3
1
2
3
5
说明/提示
数据规模：
对于所有数据，\(N<=1000\) 。
对于 \(20\%\) 数据，有 \(N<=20\) ；
对于 \(50\%\) 数据，有 \(N<=200\) ；
对于 \(30\%\) 数据，有对于所有路径最多存在两个 \(/\)（包含第 \(1\) 个字符）。
————————————————————————————————
有两种比较显然的做法，第一种是直接用 \(set\) 容器存储每个文件夹的绝对路径，然后每次按顺序判断是否需要新建。
第二种是用 \(Trie\) 的结构来实现，并且这棵字典树只需要支持插入和计数操作，所以代码非常短。
理论上来讲后者的时空复杂度都是优于前者的，但是由于数据比较小，经测试实际前者更优。
这里给出第二种做法，使用了 \(map\) 容器把字符串映射为树节点的编号，方便插入和判重处理。
代码如下：
#include <bits/stdc++.h>
#define MAXN 100007
using namespace std;
int n,cnt;
map<string,int> G[MAXN];
void Find(int &now,string ob) {
//当前在编号为 now 的目录下查找名为 ob 的文件夹
if (!G[now].count(ob)) G[now][ob]=++cnt;
now=G[now][ob];
}
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
string s; cin>>s,s+='/'; //方便后面的代码处理，字符串尾部加个'/'
int len=(int)s.size(),now=0,pt=1;
for (int i=1;i<=len;i++)
if (s[i]=='/') Find(now,s.substr(pt,i-pt)),pt=i+1;
printf("%d\n",cnt); //cnt 为当前已经创建的文件夹数量
}
return 0;
}