Alan Lee

寻找所有公共子序列并返回索引

2020/05/22 Share

最近同事说了这么一个需求:假设有两个字符串 target 和 source,要在 source 中寻找 target,但不要求 target 在 source 中是连续的,并返回索引。一般来说 target 是一个较短的词语,source 是一个包含 target 的较长句子,target 在 source 中不一定连续,且可能有多个。

例如:

1
2
3
4
target = '违禁词'
source = 'asdf违asdf禁aa词as违1禁2词3'
# 要求的返回是
wanted = ['违禁词', '违禁词'], [[4, 9, 12], [15, 17, 19]]

刚开始我觉得这是一个寻找最长公共子序列的问题,但是尝试了一下后发现,如果 source 中有多个子序列形式的 target,最长公共子序列算法只能找到其中一个,而且一般是不能返回索引的。

于是我自己重新写了一个程序来实现这个需求。程序应该不是最优的,欢迎提出改进。

大致流程:

  1. target 扩展到 ≤ len(source) 长度。
  2. target 的第一个字符 i 开始遍历。
  3. 如果 isource 中,那么记录其索引,将其加入到当前已找到的字符串 current_found 中。计算其真实索引(基于原 source),加入到 current_indices
  4. 将该字符及前面的字符从 source 中删除,成为新的 source
  5. 如果当前已找到的字符串 current_foundtarget 相等,则就找到了一个 base_target。将相关变量置为初始状态。
  6. 如果 source 为空或者长度小于 base_target 长度或者已不包含 base_target 中任何字符,结束。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def find_subsequences(source, target):
"""在 source 中找到所有子序列形式的 target,并返回索引。"""
base_target = target
target = base_target * (len(source) // len(base_target))
source_len = len(source)
all_found = []
current_found = ''
all_indices, current_indices = [], []
for i in target:
if i in source:
current_found += i
index = source.index(i)
current_indices.append(source_len - (len(source) - index))
source = source[(index+1):]
if current_found == base_target:
all_indices.append(current_indices)
all_found.append(base_target)
current_found = ''
current_indices = []
if not source or len(source) < len(base_target) or not set(source).intersection(set(base_target)):
break
return all_found, all_indices

还用上面的例子进行测试:

1
2
>>> find_subsequences(source, target)
(['违禁词', '违禁词'], [[4, 9, 12], [15, 17, 19]])

此外,关于计算真实索引:

compute real index

END

CATALOG
  1. 1. END