用於替換字符串中的匹配模式的算法

Question

什麼是在字符串上實現查找/替換算法的簡單方法？我想使用定義替換規則的字典來轉換字符串。問題是，每次更換後，我都必須確保後續替換操作在原始字符串上。例如：

我的字符串是：ABCABCDEFDEF

我的規則是：ABC - > DEF與DEF - > XXX

所以我的結果應該是：DEFDEFXXXXXX 而不是XXXXXXXXXXXX（這將是結果如果我首先應用規則一，然後應用規則二）。

Answer 1

簡單的方法：

• 在第一個字符開始，嘗試每一個關鍵，如果它發生在那個位置。

• 如果你找到一個匹配，更換，並以字符繼續更換後

• 否則，繼續下一個字符

要記住KEP：

• 歧義：如果您同時擁有「AB」和「ABC」作爲鍵，您需要決定哪些符合「ABCD」。通常你希望更長的字符串匹配（否則，它永遠不會匹配）

• Unicode：首先標準化鍵和原始字符串。

這對於少數幾個鍵肯定是足夠的。但是，它是O（N * M），其中N是字符串長度，M是替換的數量。

---

改進：

• 沒有爲比賽線性搜索;而是使用排序的鍵列表對原始字符串中的字符進行二分搜索，然後進行下一個等等。事實上，只記住第一遍中找到的匹配的位置和鍵可能是有益的，並且執行替換在第二遍

• 與許多替代品的大字符串，它通常是更好地建設一個新的字符串

• 使用Aho-Corasick搜索。這利用了有限的搜索空間（即，e知識來源於關鍵字列表）以避免探測源字符串的每個字符

Answer 2

根據您使用的語言，可能會有如此預先設計的功能。如果您使用的是C＃，則String.Replace可能會有所幫助。這會爲你節省很多時間。如果你仍然在尋找可以在其他字符串中找到模式的算法，那麼Horspool算法可能就是你正在尋找的。

您仍然必須實施後續替換操作原始字符串的邏輯。但這聽起來不是一件難事。