#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define pb push_back
#define PII pair<int, int>
#define PDI pair<double, int>
#define all(x) x.begin(), x.end()
#define quickcin() ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e4 + 10, MINRAND = 0, MAXRAND = 1e9;

mt19937 rnd1(time(0));
mt19937_64 rnd2(time(0));
uniform_int_distribution<> int_mt(MINRAND, MAXRAND);
uniform_real_distribution<> double_mt(MINRAND, MAXRAND);

int n, type;
struct node
{
    string name, path, go;
    unordered_map<string, node *> son;
};
unordered_map<string, node *> mp;
unordered_map<string, int> mp2;
vector<string> ans;
string dfs(node *u)
{
    if (!u->son.size())
    {
        return "#";
    }
    string roads = "";
    vector<string> path;
    for (auto i : u->son)
    {
        path.push_back(i.first + '/' + dfs(i.second) + '/');
    }
    sort(all(path));
    for (auto i : path)
    {
        roads += i;
    }
    mp2[roads]++;
    u->go = roads;
    return roads;
}
void dfs2(node *u)
{
    if (mp2[u->go] >= 2)
    {
        ans.push_back(u->path);
        return;
    }
    for (auto i : u->son)
    {
        dfs2(i.second);
    }
    return;
}
void solve()
{
    string s;
    cin >> n;
    // 建树
    node *root = new node();
    for (int i = 1; i <= n; i++)
    {
        cin >> s;
        node *cur = root;
        size_t pos = 1;
        while (pos < s.size())
        {
            size_t nepos = s.find('/', pos);
            string dir = s.substr(pos, nepos - pos);
            if (!cur->son.count(dir))
            {
                cur->son[dir] = new node();
                cur->son[dir]->name = dir;
                cur->son[dir]->path = s.substr(0, nepos == string::npos ? s.size() : nepos);
            }
            cur = cur->son[dir];
            pos = nepos == string::npos ? s.size() : nepos + 1;
        }
    }
    dfs(root);
    dfs2(root);
    sort(all(ans), less<string>());
    if (!ans.size())
        cout << "NotFound";
    else
    {
        for (auto i : ans)
        {
            cout << i + '/' << endl;
        }
    }
}

signed main()
{
    quickcin();
    int _ = 1;
    // cin >> _;
    while (_--)
    {
        solve();
    }
}

题面解释:

在某文件系统中，存在一些重复的文件夹，重复文件夹的定义为：如果两个或多个文件夹包含相同的非空子文件夹，并且这些子文件夹的结构也相同，则这些文件夹被认为是重复的。输入由多行组成，第一行是文件夹路径的数量 $n$，接下来的 $n$ 行是各个文件夹的路径。路径以 "/" 开头和结尾，中间每层由 "/" 分隔。输出所有重复文件夹的父路径，按字典升序排列；如果不存在重复的文件夹，则输出“NotFound”。

思路:序列化唯一表示树

问题本质为：构建出文件目录树后，询问有多少个子树，忽略根节点以后，他们的子树完全相等。

一个朴素的思路是枚举所有子树，然后进行递归check。

但是这个方法的时间复杂度过高$O(n^3)$，需要优化，考虑对每个子树进行一个序列化表示 + 哈希。然后再枚举子树 + 哈希值判定。

伪代码如下

# 定义函数 is_the_same，用于判断两个子树 node1 和 node2 是否相同
def is_the_same(node1, node2):
    # 对 node1 和 node2 的子节点分别进行排序，确保子节点的顺序一致
    sorted_son_node1 = sorted(node1.son)  # 将 node1 的子节点按名称排序
    sorted_son_node2 = sorted(node2.son)  # 将 node2 的子节点按名称排序
    
    # 如果两个节点的子节点数量不同，直接返回 False，说明不是相同子树
    if len(sorted_son_node1) != len(sorted_son_node2):
        return False
    
    # 逐个比较每一对排序后的子节点
    for i in range(len(sorted_son_node1)):
        # 如果当前子节点的名称不同，返回 False，说明子树不同
        if sorted_son_node1[i].name != sorted_son_node2[i].name:
            return False
        
        # 递归比较当前子节点的子树是否相同，如果有任意一个子树不相同，返回 False
        if is_the_same(sorted_son_node1[i], sorted_son_node2[i]) == False:
            return False
    
    # 如果所有子节点都相同且对应子树也相同，返回 True，表示两棵树相同
    return True

# 双重循环枚举树中所有节点的组合
for i in node:
    for j in node:
        # 调用 is_the_same 函数比较节点 i 和 j 的子树是否相同
        if not is_the_same(i, j):
            record(i)
            record(j)

return record.set()

题解

本题的核心在于构建一个文件目录树，并找出其中重复的子树。重复子树的定义为：如果某个子树结构完全相同，并且含有相同的子文件夹（忽略根节点），则这些子树被认为是重复的。为了有效检测这些重复的子树，我们采用以下步骤：

1. 树节点定义：使用 TreeNode 结构体来表示每个文件夹，存储子文件夹的信息，包括路径和是否为重复子树的标志。

2. 序列化树结构：通过递归遍历树的方式，将每个子树序列化为一个唯一的字符串表示。这一过程中，我们将子节点的序列化结果排序并组合，以确保相同结构的子树能生成相同的字符串。

3. 重复检测：使用哈希表存储已序列化的子树。如果再次遇到相同的序列化结果，则标记这些树节点为重复的。

4. 结果收集：遍历整棵树，找到所有标记为重复的子树，并将其父节点路径收集到结果中。

5. 输出结果：对结果进行排序，并输出每个重复子树的父路径。如果没有重复子树，则输出“NotFound”。

具体步骤:

1.构建文件目录树：通过读取输入的路径信息，将其分层解析并逐级添加到树节点中，每个路径的层级信息通过 / 分割，并逐级构建树节点。

2.子树的序列化表示：对于每个节点，通过递归的方式序列化其所有子节点，将该节点的结构和内容唯一表示成一个字符串。子节点的序列化结果会拼接并排序，保证相同结构的子树在不同位置也能得到相同的序列化字符串。

3.利用哈希表检测重复子树：每棵子树的序列化字符串作为哈希表的键值，若相同的序列化字符串已经出现，则将该子树标记为重复，并记录其父节点路径。

4.输出所有重复子树的父节点路径：遍历整棵树，查找被标记为重复的子树，记录其父节点路径，若没有重复子树则输出 "NotFound"，否则按字典序输出所有父节点路径。

代码

cpp

#include <iostream>   // 用于输入输出
#include <unordered_map>  // 哈希表
#include <vector>     // 动态数组
#include <string>     // 字符串操作
#include <algorithm>  // sort排序函数

using namespace std;

// 树节点结构体
struct TreeNode {
    unordered_map<string, TreeNode*> children; // 存储子节点
    string path;   // 当前节点路径
    bool isDuplicate;  // 标记是否为重复子树

    // 构造函数初始化
    TreeNode() : isDuplicate(false) {}
};

// 存储序列化子树的哈希表，用于检测重复
unordered_map<string, TreeNode*> duplicates;  

// 序列化树结构，将其转为唯一字符串表示
string serialize(TreeNode* root) {
    if (root->children.empty()) return "#";  // 如果没有子节点，返回 "#"

    vector<string> paths; // 存储所有子节点的序列化结果

    // 遍历所有子节点并进行序列化
    for (const auto& child : root->children) {
        paths.push_back(child.first + "(" + serialize(child.second) + ")");
    }

    sort(paths.begin(), paths.end());  // 排序确保结构唯一性

    string serialized; // 存储最终的序列化字符串
    for (const auto& p : paths) {
        serialized += p;  // 组合所有子节点的序列化字符串
    }

    // 检测是否已有相同结构的子树
    if (duplicates.count(serialized)) {
        duplicates[serialized]->isDuplicate = true;  // 标记为重复
        root->isDuplicate = true;  // 当前节点也标记为重复
    } else {
        duplicates[serialized] = root;  // 存储序列化结果
    }
    return serialized; // 返回序列化字符串
}

// 查找所有重复子树的父节点路径
void findParentDuplicates(TreeNode* root, vector<string>& result) {
    if (root->isDuplicate) {  // 如果当前节点是重复子树，加入结果
        result.push_back(root->path); // 添加父节点路径到结果
        return;
    }
    // 递归检查所有子节点
    for (const auto& child : root->children) {
        findParentDuplicates(child.second, result);
    }
}

int main() {
    int n;
    cin >> n;  // 输入路径数量

    TreeNode* root = new TreeNode();  // 初始化根节点

    // 构建树结构
    for (int i = 0; i < n; ++i) {
        string path;
        cin >> path;  // 输入每条路径
        TreeNode* curr = root; // 当前节点指向根节点
        size_t pos = 1; // 路径的开始位置，跳过第一个 '/'
        
        // 根据路径层级逐级创建树节点
        while (pos < path.size()) {
            size_t nextPos = path.find('/', pos); // 找到下一个 '/'
            string dir = path.substr(pos, nextPos - pos); // 提取当前文件夹名称
            if (!curr->children.count(dir)) {  // 如果节点不存在，则创建
                curr->children[dir] = new TreeNode();
                curr->children[dir]->path = path.substr(0, 
                                nextPos == string::npos ? path.size() : nextPos);
            }
            curr = curr->children[dir];  // 进入下一层节点
            pos = nextPos == string::npos ? path.size() : nextPos + 1; // 更新位置
        }
    }

    serialize(root);  // 序列化整棵树
    vector<string> result; // 存储重复子树的父节点路径
    findParentDuplicates(root, result);  // 查找重复子树的父节点

    sort(result.begin(), result.end());  // 结果排序
    if (result.empty()) {
        cout << "NotFound" << endl;  // 无重复子树
    } else {
        for (const auto& r : result) {
            cout << r << "/" << endl;  // 输出重复子树的父节点路径
        }
    }

    return 0; // 程序结束
}

python

# 导入 defaultdict 来构建树形结构
from collections import defaultdict

# 读取输入路径的数量
n = int(input())

# 定义一个 Node 类表示文件夹节点
class Node:
    def __init__(self):
        self.name = ""  # 当前文件夹的名称
        # to 表示从当前节点到其子节点的字典，键是文件夹名，值是 Node 对象，子文件夹存储于此
        self.to = defaultdict(Node)
        # is_duplicate 标志当前节点是否是重复文件夹
        self.is_duplicate = False

# 初始化根节点，根目录用 "root" 作为名称
root = Node()
root.name = "root"

# 创建一个字典 book，用于存储子树结构的序列化字符串
book = defaultdict(str)

# 构建文件夹结构树
for _ in range(n):
    # 读取路径并分割，去掉前后的空元素 '/'，只保留中间的部分
    paths = input().split("/")
    paths = paths[1:-1]  # 删除第一个空元素和最后一个空元素
    now = root  # 从根节点开始插入文件夹路径
    for path in paths:
        # 如果当前子文件夹不存在，创建新的节点
        if path not in now.to:
            now.to[path] = Node()  # 新节点
            now.to[path].name = path  # 设置新节点的名字
        # 继续深入到子文件夹
        now = now.to[path]

# 序列化文件夹树结构函数，用于比较文件夹结构是否相同
def serialize(root):
    ser_arr = []  # 存储当前节点下所有子树的序列化字符串
    # 遍历当前节点的子节点
    for v in root.to:
        # 递归获取子节点的序列化字符串
        ser_arr.append(serialize(root.to[v]))
    ser_arr.sort()  # 将子树按字典序排序，保证同一结构的文件夹顺序一致
    ser_str = ""  # 初始化序列化字符串
    # 拼接所有子文件夹的序列化结果
    for s in ser_arr:
        ser_str += s

    # 如果当前节点有子文件夹
    if ser_str != "":
        # 检查当前序列化结果是否已经存在
        if ser_str in book:
            # 如果存在相同的子树结构，标记该节点及其之前记录的节点为重复
            book[ser_str].is_duplicate = True
            root.is_duplicate = True
        else:
            # 如果不存在相同的子树结构，记录当前序列化结果
            book[ser_str] = root
    # 返回当前节点的序列化形式 "文件夹名称(子文件夹序列化)"
    return root.name + "(" + ser_str + ")"

# 保存重复文件夹路径的结果列表
res = []

# 查找并标记重复文件夹的函数
def find_duplicate(root, path):
    global res
    # 如果不是根目录，将当前路径加入 path
    if root.name != "root":
        path += root.name + "/"
    # 如果当前节点是重复文件夹，保存路径并返回
    if root.is_duplicate:
        res.append(path)
        return
    # 递归检查当前节点的子文件夹
    for v in root.to:
        find_duplicate(root.to[v], path)

# 序列化整个文件夹树，从根开始
serialize(root)
# 从根节点开始查找所有重复的文件夹，并记录其路径
find_duplicate(root, "/")

# 按字典序排序结果
res.sort()

# 如果找到重复文件夹，按行输出结果，否则输出 "NotFound"
if len(res) != 0:
    print("\n".join(res))
else:
    print("NotFound")

java

import java.util.*;

// 用于表示树的节点
class TreeNode {
    Map<String, TreeNode> children; // 存储子节点
    String path; // 当前节点路径
    boolean isDuplicate; // 标记是否为重复子树

    TreeNode() {
        children = new HashMap<>();
        isDuplicate = false;
    }
}
public class Main{
    
        // 存储序列化子树，检测重复
        static Map<String, TreeNode> duplicates = new HashMap<>();

        // 序列化树结构，将其转为唯一字符串表示
        public static String serialize(TreeNode root) {
            if (root.children.isEmpty()) return "#"; // 如果没有子节点，返回 "#"

            List<String> paths = new ArrayList<>();
            // 遍历所有子节点
            for (Map.Entry<String, TreeNode> child : root.children.entrySet()) {
                paths.add(child.getKey() + "(" + serialize(child.getValue()) + ")");
            }
            Collections.sort(paths); // 排序确保结构唯一性

            StringBuilder serialized = new StringBuilder();
            for (String p : paths) {
                serialized.append(p); // 组合所有子节点的序列化字符串
            }

            // 检测是否已有相同结构的子树
            if (duplicates.containsKey(serialized.toString())) {
                duplicates.get(serialized.toString()).isDuplicate = true; // 标记为重复
                root.isDuplicate = true;
            } else {
                duplicates.put(serialized.toString(), root); // 存储序列化结果
            }
            return serialized.toString();
        }

        // 查找所有重复子树的父节点路径
        public static void findParentDuplicates(TreeNode root, List<String> result) {
            if (root.isDuplicate) { // 如果是重复子树，加入结果
                result.add(root.path);
                return;
            }
            // 递归检查所有子节点
            for (TreeNode child : root.children.values()) {
                findParentDuplicates(child, result);
            }
        }

        public static void main(String[] args) {
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt(); // 输入路径数量

            TreeNode root = new TreeNode(); // 初始化根节点

            // 构建树结构
            for (int i = 0; i < n; ++i) {
                String path = scanner.next(); // 输入每条路径
                TreeNode curr = root;
                int pos = 1;

                // 根据路径层级逐级创建树节点
                while (pos < path.length()) {
                    int nextPos = path.indexOf('/', pos);
                    String dir = path.substring(pos, nextPos == -1 ? path.length() : nextPos);
                    if (!curr.children.containsKey(dir)) { // 如果节点不存在，则创建
                        curr.children.put(dir, new TreeNode());
                        curr.children.get(dir).path = path.substring(0, nextPos == -1 ? path.length() : nextPos);
                    }
                    curr = curr.children.get(dir); // 进入下一层节点
                    pos = nextPos == -1 ? path.length() : nextPos + 1;
                }
            }


            String serializedTree = serialize(root); // 序列化整棵树
            List<String> result = new ArrayList<>();
             findParentDuplicates(root, result); // 查找重复子树的父节点

            Collections.sort(result); // 结果排序

            if (result.isEmpty()) {
                System.out.println("NotFound"); // 无重复子树
            } else {
                for (String r : result) {
                    System.out.println(r + "/"); // 输出重复子树的父节点路径
                }
            }
            scanner.close();
        }

}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。