找到字符串數組中的字符串的最快算法？

這個問題只是關於算法。在僞碼是這樣的：找到字符串數組中的字符串的最快算法？

A = Array of strings; //let's say count(A) = N 
S = String to find; //let's say length(S) = M 

for (Index=0; Index<count(A); Index++) 
    if (A[Index]==S) { 
    print "First occurrence at index\x20"+Index; 
    break; 
    }

這對於迴路需要字符串比較N次（或字節比較N * M次，O（N * M））。當數組A有很多項目，或者當字符串S太長時，這是不好的。

任何找到第一個出現的更好方法？ O（K * logK）上的一些算法是可以的，但是在O（K）或O（logK）時最好，其中K是N或M.

我不介意在某些其他結構中添加或在比較循環之前做一些數據處理。

來源

2012-04-28 jondinham

「當字符串S太長時」是不相關的，除非'A中有很多字符串'具有相同的長度和相同的長前綴。（如果長度不同，則字符串相等性檢查可以立即終止，或者一旦發現不匹配，就立即終止。） – Dougal 2012-04-28 18:43:58

爲什麼使用'\ x20'而不是空格？我很好奇:-) – 2012-04-28 18:46:01

哦，是的，比較時間更多地取決於陣列中的字符串的長度A – jondinham 2012-04-28 18:46:24

您可以將整個字符串數組轉換爲有限狀態機，其中轉換是字符串的字符，並將生成狀態的字符串的最小索引置於狀態。這需要很長時間，並且可能被視爲索引。

來源

2012-04-28 18:42:49 Reactormonk

更多地被稱爲[trie]（http://en.wikipedia.org/wiki/Trie）。 – Dougal 2012-04-28 18:47:02

[f] lex可以幫助您構建此DFA。 – wildplasser 2012-04-28 18:47:06

@Dougal感謝您的名字，不知道。 – Reactormonk 2012-04-28 19:20:00

將字符串放入基於散列的集合中，並測試以查看給定字符串是否包含在集合中，一旦集合被構建，應該會給您提供更多或更少的恆定性能。

來源

2012-04-28 18:40:46 Bill

如果您想查找索引，請使用基於哈希的字符串字典 - >第一次出現。 – Dougal 2012-04-28 18:41:21

但我有點擔心有些2個項目可能具有相同的散列值 – jondinham 2012-04-28 18:44:08

那麼，你需要做最後的比較，給定相同的散列值。 – wildplasser 2012-04-28 18:46:17

您可以先排序字符串數組，這將花費O（m * nlogn）時間。在A排序之後，您可以執行二分搜索而不是線性搜索，這可以將總運行時間減少到O（m * logn）。

這種方法的優點是它很容易實現。例如，在Java中，只需2行代碼即可完成此操作：

Arrays.sort(A); 
int index = Arrays.binarySearch(A, "S");

來源

2012-04-28 18:57:44 Nova2358

二進制搜索之前的排序過程佔用大部分時間，是不是 – jondinham 2012-04-28 19:25:02

@PaulDinh它需要O（M N log N）時間。 – Dougal 2012-04-28 19:27:01

@PaulDinh我認爲在實踐中時間確定。在最壞的情況下，它的劑量需要O（M N log N）時間。但加載所有的字符串將需要M * N次，所以它只比log IO記錄長n倍。在大多數情況下，log n非常小，甚至可能比在實踐中構建一個trie或hashtable更快。如果你關心理論上的時間複雜度，那麼建立一個特里或散列表將花費O（M * N）時間。 – Nova2358 2012-04-29 03:11:01

您可以使用Self-balancing binary search tree。大多數實現都要插入O（log（n）），並且要O（log（n））進行搜索。如果你的集合不是很大，並且你的值有很好的散列函數，那麼基於散列的集合是一個更好的解決方案，因爲在這種情況下，你將有O（1）插入和O（1）尋找。但是如果你的散列函數不好，或者你的散列函數太大，那麼插入O（n）就可以搜索。

來源

2012-04-28 19:02:57

以儘可能快的搜索，最好的辦法，是讓數組排序正如你所說，似乎是沒有可能的信息先驗這將允許在搜索

排序一些啓發或約束數組第一個（快速排序例如O（NlogN）），並執行二進制搜索接下來O（log（N））

來源

2012-04-28 19:06:13 jpmuc

找到字符串數組中的字符串的最快算法？

回答

相關問題