摘要: 判断集合中存在重复是常见编程任务之一，当集合中数据量比较大时我们通常希望少进行几次扫描，这时双重循环法就不可取了。
位图法比较适合于这种情况，它的做法是按照集合中最大元素max创建一个长度为max+1的新数组，然后再次扫描原数组，遇到几就给新数组的第几位置上1，如遇到5就给新数组的第六个元素置1，这样下次再遇到5想置位时发现新数组的第六个元素已经是1了，这说明这次的数据肯定和以前的数据存在着重复。这种给新数组初始化时置零其后置一的做法类似于位图的处理方法故称位图法。它的运算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提高一倍。
阅读全文
摘要: 求两字符串的公共子串，如abc123与123456的公共字串为123，基本想法是在长的字符串前面加上长度等于短字符串的空格前缀，然后拿短字符串与新字符串挨个匹配，匹配上的置上匹配字符，否则置上空格，这样的新串就包含了匹配字串和空格，再劈分放入set即可，重复的元素会被set略过去。
阅读全文