快速字符串搜索？

我有字符串矢量和必須檢查如果向量中的每個元素的存在5000個字的給定列表。除了兩個嵌套循環的普通方法，有沒有更快的方式來做到這一點在C + +？快速字符串搜索？

來源

2013-02-05 ofey

是它擺在首位，而不是一個列表來填充關聯容器的選擇嗎？ –

是否可以對5000個單詞列表進行排序？如果是，那麼在排序列表中，您可以在向量中查找字符串。 – Satyajit

你希望字符串匹配*一個完整的*在你的設置，或者是它足夠的組中的一個*包含*一個你正在尋找？ –

你應該把字符串列表到std::set。這是一個針對搜索進行優化的數據結構。查找給定元素是否在集合中是一種比迭代所有條目快得多的操作。

當您已經在使用C++ 11時，您還可以使用std::unordered_set，因爲它是作爲散列表實現的，所以查找速度更快。

這應該是針對學校/大學的：準備好解釋這些數據結構如何加快速度。當你的導師要求你解釋你爲什麼使用他們時，「互聯網上的一些人告訴我」在課本中不太可能爲你贏得一張貼紙。

來源

2013-02-05 21:11:40 Philipp

哈哈，不，如果這是爲了學校，會提到它。這是我的一個usaco問題代碼的一部分。 – ofey

你可以把單詞列表中的std::unordered_set。然後，對於向量中的每個元素，只需測試它是否在O（1）的unordered_set中。你會有一個預期的O（n）複雜性（看看評論，看看爲什麼它只是預期）。

來源

2013-02-05 21:13:24

這並不完全是事實。必須計算每個字符串的散列值，並且必須至少比較一次字符串。每一個都與字符串總數無關（在預期的情況下），但值得一提的是。雖然最糟糕的情況極不可能，但保持正確並說*預期*時間爲O（1）是很好的風格。 – delnan

你完全正確。結果我改變了我的答案。謝謝。 –

你可以排序的載體，那麼你可以用一個「循環」解決這個問題（採取了你的字典是太排序），這意味着爲O（n）在排序的成本不計。

來源

2013-02-05 21:23:31 hege

所以，你有一個字符串矢量，具有一個或多個字，每個字符串，你有一個載體，這是一個字典，你應該確定哪些單詞在字符串中的向量也都在字典？字符串的矢量是一個煩惱，因爲你需要看每個單詞。我首先創建一個新的矢量，將每個字符串拆分爲單詞，並將每個單詞推入新的矢量。然後對新矢量進行排序並通過std::unique算法運行以消除重複。然後對字典進行排序。然後通過std::set_intersection同時運行範圍寫的結果。

來源

2013-02-05 21:46:11

快速字符串搜索？

回答

相關問題