kipsora 最近的时间轴更新
kipsora

kipsora

V2EX 第 263363 号会员,加入于 2017-10-29 20:46:13 +08:00
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 应该是竞赛题中的做法
2020-09-08 04:03:22 +08:00
回复了 zxCoder 创建的主题 问与答 关于 Online Judge 判题沙箱的学习问题
参考一下 VFleaKing 的 UOJ 的沙箱?我很久之前自己仿(chao)造(xie)了一个,docker 可能没办法很好地测量时间和峰值内存吧,自己写隔离肯定不太行,所以比较理想的方案是在 docker 中跑沙箱(或者你对自己的沙箱足够自信也可以不用 docker )。

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

不过我觉得从头造轮子这件事,用来学习一下操作系统编程感觉还行,真的要用不如先参考一下市面上有没有现成能拿来用的 OJ,自己写的 OJ 一是你走了之后维护会很麻烦,最后可能也没啥人用。
2020-09-03 13:28:21 +08:00
回复了 LMuyi 创建的主题 NVIDIA 6.1 入的 1.1W 2080ti O11G
换个思路,现在再入一块 2080Ti 就可以平衡损失了(狗头
2020-05-03 13:20:10 +08:00
回复了 SouthCityCowBoy 创建的主题 问与答 IPS 硬屏的抗压程度如何?
用显示器测试的网站看看有没有坏点之类的?我觉得如果肉眼看不出来真的没有必要纠结,毕竟背板漏光给你带来的影响可能会更大。我自己有台 LG UL850,我偶尔会不小心用指甲或者笔记本的金属边框划到两下屏幕但并没有任何划痕,希望能给你些参考
2020-05-03 13:05:18 +08:00
回复了 kipsora 创建的主题 问与答 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管?
@glasswm 谢谢你的经验,我觉得我跟你的 case 应该挺像的。请问一下你的 NAS 用的是啥?黑群? FreeNAS ?
2020-05-03 13:03:20 +08:00
回复了 kipsora 创建的主题 问与答 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管?
@hanqi7012 我发现群晖某些产品用的是 ARM 的 CPU,我之前在树莓派上跑 docker 很多镜像都不能在 ARM 上跑。。
2020-05-03 13:01:45 +08:00
回复了 kipsora 创建的主题 问与答 想买个 HPE Proliant Microserver Gen10 PLUS 做 NAS 和 GitLab 托管?
@WebKit DS918+ 的价格在我这(加拿大)快可以买 2 台 Gen10 了(加拿大的定价很奇怪而且消费税挺高),但 Plus 的价格确实差不多(前面把 Plus 的价格看错了)
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1614 人在线   最高记录 6543   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 12ms · UTC 16:52 · PVG 00:52 · LAX 09:52 · JFK 12:52
Developed with CodeLauncher
♥ Do have faith in what you're doing.