摘要: 判斷集合中存在重復是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然后再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重復。這種給新數組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。
閱讀全文
摘要: 求兩字符串的公共子串，如abc123與123456的公共字串為123，基本想法是在長的字符串前面加上長度等于短字符串的空格前綴，然后拿短字符串與新字符串挨個匹配，匹配上的置上匹配字符，否則置上空格，這樣的新串就包含了匹配字串和空格，再劈分放入set即可，重復的元素會被set略過去。
閱讀全文