合并子目录(hash)

题目2 : 合并子目录

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

小Hi的电脑的文件系统中一共有N个文件，例如：

/hihocoder/offer22/solutions/p1

/hihocoder/challenge30/p1/test

/game/moba/dota2/uninstall

小Hi想统计其中一共有多少个不同的子目录。上例中一共有8个不同的子目录：

/hihocoder

/hihocoder/offer22

/hihocoder/offer22/solutions

/hihocoder/challenge30

/hihocoder/challenge30/p1

/game

/game/moba

/game/moba/dota2/

输入

第一行包含一个整数N (1 ≤ N ≤ 10000)

以下N行每行包含一个字符串，代表一个文件的绝对路径。保证路径从根目录"/"开始，并且文件名和目录名只包含小写字母和数字。

对于80%的数据，N个文件的绝对路径长度之和不超过10000

对于100%的数据，N个文件的绝对路径长度之和不超过500000

输出

一个整数代表不同子目录的数目。

样例输入

3  
/hihocoder/offer22/solutions/p1   
/hihocoder/challenge30/p1/test  
/game/moba/dota2/uninstall

样例输出

//看似挺复杂的，其实，用简单的方法做即可，hash，万一冲突了，换个权，再来一次，哈哈，学到了

 1 # include <cstdio>
 2 # include <cstring>
 3 # include <cstdlib>
 4 # include <iostream>
 5 # include <vector>
 6 # include <queue>
 7 # include <stack>
 8 # include <map>
 9 # include <bitset>
10 # include <sstream>
11 # include <set>
12 # include <cmath>
13 # include <algorithm>
14 #pragma comment(linker,"/STACK:102400000,102400000")
15 using namespace std;
16 #define LL          long long
17 #define lowbit(x)   ((x)&(-x))
18 #define PI          acos(-1.0)
19 #define INF         0x3f3f3f3f3f3f3f3f
20 #define eps         1e-8
21 #define MOD         1000000007
22 
23 inline int scan() {
24     int x=0,f=1; char ch=getchar();
25     while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
26     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
27     return x*f;
28 }
29 inline void Out(int a) {
30     if(a<0) {putchar('-'); a=-a;}
31     if(a>=10) Out(a/10);
32     putchar(a%10+'0');
33 }
34 #define MX 500005
35 /**************************/
36 
37 set<LL>ss;
38 char s[MX];
39 
40 int main ()
41 {
42     int n;
43     scanf("%d",&n);
44     for (int i=1;i<=n;i++)
45     {
46         scanf("%s",s);
47         LL _hash=0;
48         for (int i=1; s[i]; ++i) {
49             if (s[i]=='/') ss.insert(_hash);
50             _hash=_hash*132+s[i];
51         }
52     }
53     printf("%d
",ss.size());
54     return 0;
55 }

View Code