string - 替换字符串中匹配模式的算法

Question

在字符串上实现查找/替换算法的简单方法是什么？我想使用定义替换规则的字典转换字符串。问题是每次替换后，我必须确保后续替换对原始字符串进行操作。例如:

我的字符串是:ABCABCDEFDEF

我的规则是:ABC -> DEF 和 DEF -> XXX

所以我的结果应该是:DEFDEFXXXXXX而不是 XXXXXXXXXXXX(如果我先应用规则一然后应用规则二，这将是结果)。

Answer 1

简单的方法:

• 从第一个字符开始，尝试每个键是否出现在该位置。

• 如果找到匹配，替换并继续替换后的字符

• 否则，从下一个字符继续

请记住:

• 歧义:如果您同时将“AB”和“ABC”作为键，您需要决定哪个应该匹配“ABCD”。通常你希望较长的字符串匹配(否则，它永远不会匹配)

• Unicode:首先规范化键和原始字符串。

这对于少数几个键来说肯定足够了。但是，它是 O(N*M)，其中 N 是字符串长度，M 是替换次数。

---

改进:

• 不要线性搜索匹配项；而是使用排序的键列表并对原始字符串中的字符进行二进制搜索，然后是下一个等。实际上，只记住在第一遍中找到的匹配项的位置和键并进行替换可能是有益的在第二遍中

• 对于有很多替换的大字符串，通常最好构建一个新字符串

• 使用 Aho-Corasick用于搜索。这利用了有限的搜索空间(即从关键字列表中得出的知识)来避免探测源字符串的每个字符