题目链接

题目大意

??略

解题思路

??主要是说下坑点，比如这组数据：
?? 3
?? /game/moba/dota2/a
?? /game/moba/dota2/b
?? /game/moba/dota2/c
??结果应该是
?? /game-moba-dota2/a
?? /game-moba-dota2/b
?? /game-moba-dota2/c
??如果目录下只有单一目录但是文件有多个也要合并，还有就是有可能把第一个‘/‘写成‘-‘的可能，题目不难，主要是一些细节的东西。

代码

const int maxn = 5e5+10;
const int maxm = 2e3+10;
char s[39] = "0123456789abcdefghijklmnopqrstuvwxyz/";
int trie[maxn][39], tot, num[256], n;
string ss[maxn];
void insert(string ss) {
	int p = 0;
	for (auto ch : ss) {
		if (!trie[p][num[ch]]) trie[p][num[ch]] = ++tot;
		p = trie[p][num[ch]];
	}
}
void solve(string &ss) {
	int p = 0, pre = 0, flag = 1, sz = ss.size();
	for (int i = 0; i<sz; ++i) {
		int cnt = 0;
		if (i) {
			for (int j = 0; j<39; ++j)
				if (trie[p][j]) ++cnt;
			if (cnt!=1) flag = 0;
			if (ss[i]==‘/‘) {
				if (flag) ss[pre] = ‘-‘;
				//cout << pre << endl;
				flag = 1;
				pre = i;
			}
		}
		p = trie[p][num[ss[i]]];
	}
	ss[0] = ‘/‘;
}
int main() {
	for (int i = 0; s[i]; ++i) num[s[i]] = i;
	cin >> n;
	for (int i = 1; i<=n; ++i) cin >> ss[i], insert(ss[i]);
	for (int i = 1; i<=n; ++i) {
		solve(ss[i]);
		cout << ss[i] << endl;
	}
	return 0;	
}

HihoCoder - 1559 合并子目录(字典树)

原文：https://www.cnblogs.com/shuitiangong/p/14420236.html