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

Question

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

我的字符串是：ABCABCDEFDEF

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

所以我的结果应该是：DEFDEFXXXXXX

而不是XXXXXXXXXXXX（如果我先应用规则一，然后应用规则二将是结果）。

- Simeon

---

对于每个规则，找到它匹配文本的索引，然后应用该规则？（我认为一定有更快的方法） - petabyte

每次应用规则后，我的索引都会改变，不是吗？ - Simeon

遍历整个字符串一次，并在列表或类似数据结构中记录所需子字符串的出现情况，然后遍历列表并不断进行替换！ - user2963623

创建一个有限状态机。这可以手工完成（只需要5个状态），也可以使用生成器如（f）lex完成。 - wildplasser

Answer 1

简单的方法：

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

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

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

需要注意的事情：

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

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

对于少量键来说，这肯定已经足够了。但是，它的时间复杂度是O（N*M），其中N是字符串长度，M是替换次数。

---

改进：

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

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

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

- peterchen

Answer 2

根据您使用的语言，可能有一些预定义函数可用。如果您使用的是 C#，String.Replace 可能会很有帮助。这将为您节省很多时间。如果您仍在寻找可以在其他字符串中查找模式的算法，则 Horspool 算法可能是您要寻找的。

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

- チーズパン

---

是的，我可以使用像String.Replace这样的函数，但我无法弄清楚如何独立地应用每个规则。 - Simeon

你可以保存已更改的子字符串的索引。下次遍历字符串查找另一个模式时，您可以查看子字符串是否已更改。 - チーズパン