← 返回 anthropic 的题目列表Find Duplicate Files in a File System
类型：online_judge
Problem: Find Duplicate Files in a File System
You are given descriptions of directories in a file system. Find all groups of files that have exactly the same content.
Each directory description has the following format:
root file1(content1) file2(content2) ...
Where:
root is the directory path;
fileX is a file name;
contentX is the content of that file;
one directory may contain multiple files;
two files are considered duplicates if their content strings are exactly the same.
Return all duplicate file groups. Each group must contain at least two full file paths.
Input Format
n
line_1
line_2
...
line_n
The first line contains an integer n, the number of directory descriptions;
The next n lines each describe one directory.
Output Format
Print one duplicate group per line;
Within each group, print full file paths in lexicographical order, separated by a single space;
Sort all groups by the first path in each group;
If there is no duplicate file, print EMPTY.
Constraints
1 <= n <= 2 * 10^4;
The total number of files is at most 2 * 10^5;
The total length of all input strings is at most 10^6;
Directory paths and file names do not contain spaces;
File content does not contain the right parenthesis ).
Example
Input:
4
root/a 1.txt(abcd) 2.txt(efgh)
root/c 3.txt(abcd)
root/c/d 4.txt(efgh)
root 4.txt(efgh)
Output:
root/4.txt root/a/2.txt root/c/d/4.txt
root/a/1.txt root/c/3.txt
Example
Input
4
root/a 1.txt(abcd) 2.txt(efgh)
root/c 3.txt(abcd)
root/c/d 4.txt(efgh)
root 4.txt(efgh)
Output
root/4.txt root/a/2.txt root/c/d/4.txt
root/a/1.txt root/c/3.txt