kipsora

V2 吞我缩进，放这里了 https://pastebin.com/X0hnmw6A

```python
P = 177
MOD = 192073433

def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))

pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)

sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))

disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]

hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)

disabled_hashes.update(hash_to_be_disabled)

print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))


if __name__ == "__main__":
main()
```

可能说得不是很清楚，花了点时间写了个法 2 的代码：

```python3
P = 177
MOD = 192073433

def main():
strings = input().split(",")
string_hashes = []
max_string_length = 0
for string in strings:
hashes = [0]
for i in range(len(string)):
hashes.append((hashes[-1] * P + ord(string[i])) % MOD)
string_hashes.append(hashes)
max_string_length = max(max_string_length, len(string))

pows = [1] # P ** i
for i in range(max_string_length + 1):
pows.append(pows[-1] * P % MOD)

sorted_indices = list(range(len(strings)))
sorted_indices = sorted(sorted_indices, key=lambda i: len(strings[i]))

disabled_hashes = set()
answers = [None for _ in strings]
for i in sorted_indices:
string = strings[i]
hashes = string_hashes[i]

hash_to_be_disabled = []
min_length = len(string) + 1
for x in range(len(string)):
for y in range(x, len(string)):
substr_hash = (hashes[y + 1] - hashes[x] * pows[y + 1 - x]) % MOD
substr_hash = (substr_hash + MOD) % MOD
hash_to_be_disabled.append(substr_hash)
if substr_hash not in disabled_hashes and min_length > (y - x + 1):
min_length = y - x + 1
answers[i] = (x, y)

disabled_hashes.update(hash_to_be_disabled)

print(",".join([strings[i][x: y + 1] for i, (x, y) in enumerate(answers)]))


if __name__ == "__main__":
main()
```

输入：dev1,dev2,dev3,v3a,abc,bc
输出：d,2,ev3,v,ab,b

输入：abcabc,a,ab,abc,abca,abcab
输出：cabc,a,b,c,ca,cab

输入：a,aa,aaa,aaaa,aaaaa,aaaaaa
输出：a,aa,aaa,aaaa,aaaaa,aaaaaa

输入：ab,cd,abc,cde,abcd,cdab,cdabb,cac,cab,cacd
输出：a,c,bc,e,bcd,da,bb,ca,cab,acd

题主你给的这个例子似乎也有些问题，v3 应该能同时表示 dev3 和 v3a ，而 v3a 更小，所以其实 dev3 的特征串只能是 ev3 而不能是 v3

待会要说复杂度这里先定义一些变量吧：假设我们有 n 个字符串，最长长度不超过 m ，假设这个集合不是可重集合

按长度对于从小到大考虑每个字符串。假设当前考虑字符串是 s_i ，那么现在的问题就变成了，找到 s_i 的最短字串 t 使得 t 不是 s_1 到 s_{i-1} 中任何一个字符串的字串。这个问题按照从最暴力到比较聪明的方式我大概想到了如下几种做法：

1. 直接暴力枚举每个串的特征串，这样每个串有 O(m^2) 个字串，每个字串放到前面 i-1 个字串里面跑 KMP ，需要 O(n^2m^3)（或者 O(n^2m^4) 如果直接调用朴素字符串匹配的话），楼主你这个数据量比较小这样 1 秒内应该能出结果；

2. 可以预处理每个串的 Hash ，这样我们枚举出字串之后就可以快速判断一个串是否是之前某个串的字串，注意这里计算 Hash 的方式应该是先通过计算前缀 Hash 然后计算得到子串 Hash ，这样判断字串是否存在是 O(1) 的（方法 1 是 O(m)的），这样总复杂度降低到了 O(nm^2)，关于前缀和字符串 Hash 的可以参考这里 https://blog.csdn.net/SHU15121856/article/details/109553503

3. 一个比较直观的发现是如果 s_i 的某个子串 t 不能成为 s_i 的特征，那么 t 的子串也一定不行。所以我们不用暴力枚举字串，改用双指针的做法，假设当前枚举的子串 t 的左端点是 x ，右端点是 y ，一开始 x = y = 1 （这里我是 1-based ），一开始定住 x 不动，看看 s_i[x..y] 是不是可以成为特征串，如果不行那么 y++ 直到可以。找到可以的串之后 x++，然后重复以上步骤直到 x 扫到 s_i 的最后一个字符。因此在查询完双指针表示的子串之后，只有两种可能，要么 x++ 要么 y++，所以这样最多只会有 O(m) 个子串需要查询，看起来好像我们现在达到了 O(nm) 的复杂度，但其实不然，如果按照方法 2 处理 Hash ，我们预处理的复杂度就达到了 O(nm^2)，所以总复杂度还是 O(nm^2) 的。

这里如果想要进一步优化可以上使用后缀三兄弟（后缀数组 /后缀树 /后缀自动机）：比如先对所有串建立广义后缀自动机（复杂度 O(nm)），每次 y++ 的时候直接看看 s[y] 能否在后缀自动机上走下去，走不下去了就 x++ 然后 Fail 边跳一下。这样总复杂度能做到 O(nm) 即输入复杂度。

不知道题主需要什么程度的复杂度，但 2 应该是足够用了，3 应该是竞赛题中的做法

参考一下 VFleaKing 的 UOJ 的沙箱？我很久之前自己仿(chao)造(xie)了一个，docker 可能没办法很好地测量时间和峰值内存吧，自己写隔离肯定不太行，所以比较理想的方案是在 docker 中跑沙箱（或者你对自己的沙箱足够自信也可以不用 docker ）。

具体见： https://github.com/vfleaking/uoj/tree/master/judge_client/1/uoj_judger

不过我觉得从头造轮子这件事，用来学习一下操作系统编程感觉还行，真的要用不如先参考一下市面上有没有现成能拿来用的 OJ，自己写的 OJ 一是你走了之后维护会很麻烦，最后可能也没啥人用。

换个思路，现在再入一块 2080Ti 就可以平衡损失了（狗头

用显示器测试的网站看看有没有坏点之类的？我觉得如果肉眼看不出来真的没有必要纠结，毕竟背板漏光给你带来的影响可能会更大。我自己有台 LG UL850，我偶尔会不小心用指甲或者笔记本的金属边框划到两下屏幕但并没有任何划痕，希望能给你些参考

@glasswm 谢谢你的经验，我觉得我跟你的 case 应该挺像的。请问一下你的 NAS 用的是啥？黑群？ FreeNAS ？

@hanqi7012 我发现群晖某些产品用的是 ARM 的 CPU，我之前在树莓派上跑 docker 很多镜像都不能在 ARM 上跑。。