咨询道友们一个算法问题：输入元素集合，输出特征短元素集合

[xabcstack]

咨询道友们一个算法问题：

输入 ｛ dev1,dev2,dev3,v3a,abc,bc ｝

期望输出 ｛ 1,2,v3,3,ab,c ｝

特征就最短最相似匹配 ，比如 1 就能代表 dev1 , 3 和 dev3 , v3a 都相似，但是 v3a 比较短，所以 3 代表了 v3a

输入的字符串元素，每个长度一般 20 个 或者 50 个左右， 整个集合长度考虑 100 个以内就行

集合，不需要一对一输出，不能丢了元素就行

[kipsora]

待会要说复杂度这里先定义一些变量吧：假设我们有 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 应该是竞赛题中的做法

[ruxuan1306]

抛砖引玉，想了个最差 O(n3)的算法，输出估计是{1, 2, 3, v, a, b}

输入串按长度排序，从短到长处理，
遍历第一个串的每个长度为 1 的子串，统计它在其它未处理串中的出现次数，
找到出现次数最少的子串，
若已被输出使用，则继续遍历第一个串的每个长度为 2 的子串，统计...
若未使用，则输出该子串，
继续下一个输入串。

[xabcstack]

@kipsora 感谢探讨，集合数据就是数学概念，三要素 确定性 互异性 无序性

@ruxuan1306 这个 a 不是特征了，因为 v2a 和 abc 都有，所有 单纯的 a 不能代表确定的某一个

[kipsora]

可能说得不是很清楚，花了点时间写了个法 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

[kipsora]

```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()
```

[kipsora]

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

[xabcstack]

@kipsora 强！ 赞！👍

[xabcstack]

@kipsora 再次感谢，使用场景用在这里了 

https://ki.xabc.io/#/changelog?id=_2021-12-10

[xabcstack]


图片不能显示吗

[xabcstack]

[image]( https://filelist.cn/disk/1/unix.jpg?key=617cd3233408c603374e3561)

[xabcstack]

<img src=https://filelist.cn/disk/1/b2fafa7dly1gx11ef0vovj20gc0m8wfn.jpg?key=61ba10e33408c60337552403 />