目录

  1. END

最近同事说了这么一个需求：假设有两个字符串 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. 如果 i 在 source 中，那么记录其索引，将其加入到当前已找到的字符串 current_found 中。计算其真实索引（基于原 source），加入到 current_indices。
  4. 将该字符及前面的字符从 source 中删除，成为新的 source。
  5. 如果当前已找到的字符串 current_found 和 target 相等，则就找到了一个 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 indexcompute real index

END