處理在海量個字符串中找到某個字符串的方法
今天收到intel面試，問我一個問題，如何在一萬個字符串中找到某個相關(guān)的字符串？當(dāng)時感覺打得不好，回頭自己又想了想，現(xiàn)寫下感想。
方法1：最笨的方法，一個一個的遍歷
方法2：采用劃分子集的方法，首先以第1個字符進(jìn)行劃分，將a到z開頭的字符串劃分到不同的子集中，然后比較，接著，再到相應(yīng)子集中進(jìn)行劃分，在比 較，一直到找到為止，這個方法相較于方法1是：1，相對于每次比較的字串而言，所有首字母不相同的不再進(jìn)行比較，比方說happy，肯定去以h為首字母的 集合中進(jìn)行比較，然后對于子串a(chǎn)ppy，只要到所有子串以a為首字母的集合中進(jìn)行比較，如此下去，時間花費(fèi)主要在于劃分子集上，而劃分子集的次數(shù)又跟 happy的長度有關(guān)系，所以只需劃分5次即可，所以時間復(fù)雜度是O(mn)，m是要尋找字符串的長度，n是原始字符串集合大小。
方法3:采用正則表達(dá)式匹配，比如還是happy，假如將原始集合中的所有字符串和正則表達(dá)式pattern = ^h[A-Za-z]+y$進(jìn)行匹配，接著在對app這個子串和子集合中進(jìn)行正則表達(dá)式匹，pattern=^a[A-Za-z]+p$,最后對p進(jìn)行匹配即可，時間復(fù)雜度O(mn)
方法4：采用Hadoop海量數(shù)據(jù)處理，將海量字符串分到不同的map任務(wù)中，每個任務(wù)，進(jìn)行對字符串在相應(yīng)的node上進(jìn)行查找，接著對于所有的map的結(jié)果交給reduce任務(wù)分析，這僅僅是個方案，具體時間復(fù)雜度的話，看你有多少個map任務(wù)了。
方案5：采用trie樹，對這海量字符串構(gòu)建一顆trie樹，然后在trie樹中查找該字符串，trie樹的優(yōu)勢在于對于前綴一樣的字符串都可以在一次匹配查找中得到，時間復(fù)雜度在于構(gòu)建trie樹復(fù)雜度，和trie樹的高度。
方案6：可以采用編譯原理學(xué)到的自動機(jī)，最近再看編譯原理突然想到，不過對于海量數(shù)據(jù)，具體情況怎么樣，還得我繼續(xù)探索~~
喜歡 
頂
難過
囧
圍觀
無聊
