搜索模式匹配的字符串「ABC：*：XYZ」在不到爲O（n）

Question

給定一串字符串，我需要找到那些匹配了3種模式，其中：

• 前綴搜索 - ABC *
• 水珠狀花紋 - ABC：*：XYZ
• 後綴搜索 - * XYZ

其中*是一個通配符（和可匹配任何數目的字符）。

現在，簡單的解決方案就是掃描每個字符串並查看它是否與目標模式相匹配。但是這是O（n）。如果我將字符串存儲在平衡搜索樹中，則可以在O（log n）中執行前綴查詢。如果我創建了一個所有字符串基本顛倒的樹，我可以在O（log n）中執行後綴查詢。有沒有一種巧妙的方法可以高效地搜索「abc：*：xyz」模式？

Answer 1

不會有其他兩個查詢的結果交叉嗎？並且由於每個結果都是O（log N），並且結果集中的結果集的交集是O（N），所以總計也不會是原始問題的O（log N）嗎？

Answer 2

如果您考慮將搜索樹中的字符串存儲起來的可能性，爲什麼不使用這些屬性作爲關鍵字來存儲屬性「以abc開頭」和「以xyz結尾」？

編輯： 您也可能想放棄Big-O-Notation，而將注意力放在您的特定用例的實際預期搜索持續時間上。這可能是更現實的方法;對於您的算法/實現而言，O（f（n））風格等級在實際搜索效率方面可能不會提供太多有用的信息。

Answer 3

如果「ABC」和「XYZ」是固定值，可以維持三個計數器與您的收藏表明串的數量：

• 開始「ABC」，但不是「XYZ」的結局。
• 不以「abc」開頭，但以「xyz」結尾。
• 以「abc」開頭並以「xyz」結尾。

這會給你一個O（1）時間複雜度，用於在插入或刪除集合時以額外計算爲代價進行搜索。

如果「abc」和「xyz」是任意字符串，則對於所有操作（包括「abc ...」）都是O（n）。你只需要考慮當你的集合包含所有以「abc」開頭的項目來看看會發生什麼。由於必須處理樹中的所有項目（每個非葉節點的兩個分支），因此完全不受O（logN）限制。

我認爲你的理想解決方案是維護兩個有序樹，一個用於正常字符串，另一個用於反轉字符串。但不要擔心試圖在兩者之間進行交叉。你所要做的就是儘可能地減少搜索空間。

• 要找到「abc ...」，請使用普通樹來查找以該值開始的字符串。
• 找到「...xyz「，使用反向樹查找以該值（zyx ...）的倒數結尾的字符串
• 要查找」abc ... xyz「，請使用普通樹來查找以該值開始的字符串值，然後過濾出那些不以「xyz」結尾的數據

這樣你就不必擔心兩棵樹之間的相交值，而且你仍然可以獲得比簡單線性搜索

Answer 4

生成每個單詞的旋轉並將每個旋轉放在後綴樹中，並指示「旋轉索引」。

例如，把字符串 「hello」，把

hello, 0 
elloh, 1 
llohe, 2 
lohel, 3 
ohell, 4 

而且，你把 「英雄」 作爲

hero, 0 
eroh, 1 
rohe, 2 
oher, 3 

而且，你把 「OHE」（不要問我有什麼OHE）

ohe, 0 
heo, 1 
eoh, 2 

然後，如果你需要搜索模式 「他* o」的，你需要直到你得到一個前綴旋轉它（ohell，4），（oher，3），（ohe，0）。在後綴樹中找到候選：（ohell，4），（oher，3），（ohe，0）。 然後你恢復它們的原始版本（通過不旋轉它們）並選擇正確的 - 「你好」和「英雄」。