给定表替换子字符串的最佳方法

Question

给出一个表格，替换单词列表中的子串的最佳/最优方法是什么。假设单词的数量可以相当大。此外，可以假设只需要1个匹配或每个单词只有1个匹配。如果找到匹配，则不需要替换或甚至检查其他子字符串。

我目前的解决方案是暴力破解，采用O(nmk)：

words = ['dfacatlgajd', 'sdfalafjump', 'adfasfhagl']

conversion = {'cat': 'dog',
              'car': 'zoom',
              'jump': 'over'}

new_words = []
for word in words:
    updated = False
    for k, v in conversion.items():
        if k in word:
            new = word.replace(k, v)
            updated = True
            new_words.append(new)
            break
    if not updated:
        new_words.append(word)

print(new_words)

输出：

['dfadoglgajd', 'sdfalafover', 'adfasfhagl']

Answer 1

如果文本的长度为n，要查找的单词集合的总长度为m，并且这些单词在文本中有k次出现，则可以使用Aho-Corasick algorithm在O(m+n+k)时间内找到所有出现的单词。如果您通过写出字符串的新版本来执行替换，这只会增加与其总长度成比例的时间。

一种不太复杂但几乎同样快的方法是应用Rabin-Karp algorithm来查找所有出现的相同长度的单词。您将需要重新运行算法(或通过维护不同长度的多个散列来交错运行)，以处理不同长度的单词。

Answer 2

我不确定这是不是一个确切的答案，但是代码块不适合注释。通过在每次循环开始时将new_word赋值给word，然后在需要时重新赋值，可以避免条件变量和标志变量：

new_words = []
for word in words:
    new_word = word
    for k, v in conversion.items():
        if k in word:
            new_word = word.replace(k, v)
            break
    new_words.append(new_word)

它似乎运行得稍微快一些，但这可能只是测量方差。(它在渐近复杂性方面没有任何不同，但条件检查确实需要时间。)我个人也觉得它读起来更干净，但你的里程数可能会有所不同。