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

Question

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

我的字符串是: ABCABCDEFDEF

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

因此，我的结果应该是: DEFDEFXXXXXX，而不是XXXXXXXXXXXX (如果我首先应用第一条规则，然后适用第二条规则，这就是结果)。

Answer 1

简单的方法：

• 从第一个字符开始，如果发生在该位置，请尝试每个键。
• 如果找到匹配，请在替换后替换并继续使用该字符。
• 否则，继续下一个字符。

记在脑海中：

• 歧义:如果您同时使用"AB“和"ABC”作为键，则需要决定哪一个应该与"ABCD“匹配。通常您希望更长的字符串匹配(否则，它永远不会匹配)
• Unicode:首先对键和原始字符串进行规范化。

这对一把钥匙来说当然足够了。但是，它是O(N*M)，其中N是字符串长度，M是替换数。

改进：

• 不要线性地搜索匹配项；而是使用一个排序的键列表，并对原始字符串中的字符进行二进制搜索，然后再进行下一个字符串等。实际上，只记住第一次传递中找到的匹配项的位置和键，并在第二次传递中执行替换操作可能是有益的。
• 对于具有多个替换的大型字符串，通常更好地构建一个新字符串。
• 使用阿霍-科拉西克进行搜索。这利用有限的搜索空间(即从关键字列表中派生的知识)来避免探测源字符串的每个字符。

Answer 2

根据您正在使用的语言，可能会有预先设计的函数。如果您使用的是String.Replace，那么C#可能会有所帮助。这能帮你节省很多时间。如果您仍然在寻找能够在其他字符串中找到模式的算法，那么霍斯波尔-algorithm可能就是您所要寻找的。

您仍然需要实现后续替换对原始字符串进行操作的逻辑。但这听起来并不难做。