說我有一個字的文件：快速檢查字符串是否包含字典文件中的單詞？
然後我有一個字符串：
I was eating some Apple-bacon when the phoNe rang.
我試圖找到一種快速的方式來產生：
I was eating some *****-***** when the ***** rang.
基本上，我試圖審查聊天框。我只是想知道是否有比遍歷矢量更好的方法。我只使用標準庫，所以推薦hashmap是不可能的。
我使用C++ 98
我只是想知道是否有更好的方法比遍歷矢量。
上排序的矢量選其一binary_search或std::set爲保證O（LG Ñ）查找時間。 lg（2000）= 7.6，理論上速度提高了263倍，忽略了任何常數因素。
（雖然這是真正的正則表達式更適合。）
的第一次嘗試是來標記短語和每一個字查找在地圖或set。
但是，如果你有一個服務器必須處理大量的消息，你可以考慮實現它更聰明一點。通過串，逐個字符走路，像一些更好的數據結構內搜索：
後綴樹應該非常快，但浪費了很多內存。哈希值可能比設置的實現更快，但是你必須想出一個聰明的算法。
有幾種備選方案，以加快搜索。
一個更簡單的方法，如果你已經有字的載體，是sort載體和做binary_search
如果要審查該字符串很長，你可以嘗試通過遍歷字符串只有一次優化。
使用您正在搜索的單詞列表中的字母構造一棵樹，並編寫一個使用此地圖查找單詞的函數。設計很複雜，但對於很長的字符串和許多單詞進行搜索可能是最快的。
實施例：
詞：猿，ACE，阿帕，通過，
樹
A B
/| |
p c y
/| |
e a e
搜索：
1）迭代槽在字符串中的每個字符爲頂層字符（A或B）
2）如果找到，檢查下一個字母是否是第一個孩子。
請注意，無論如何每個strchr都會在字符串中迭代字符，並且由於branch prediction而速度很快，應該是regexp的原始實現。
我發現它簡化了算法，使所有26+個詞根都是單根的孩子。 – 2012-01-03 16:42:26
這就是所謂的特里搜索 – stefaanv 2012-01-03 18:33:32
是的，確實如此。謝謝stefaanv。我只記得這個想法，而不是名字。 http://en.wikipedia.org/wiki/Trie – cprogrammer 2012-01-04 11:07:59
Trie搜索可能是最好的方法。建立詞典中所有單詞的樹並比較頂部的輸入。當看到非字母表字母時，重新設置並從樹的頂端再次啓動
C++ 11提供'unordered_map'。它是'標準庫'而不是'STL'。 – 2012-01-03 15:56:20
「Apple」這個詞有什麼不對？我可以考慮更嚴厲的話來審查！ – Matt 2012-01-03 16:00:50
@Matt這只是一個例子，因爲我不想寫實際的單詞。 – jmasterx 2012-01-03 16:01:58